Re: [Ocaml-lib-devel] Re: new dllist (yet again)

[Nicolas C. <war...@fr...>]

> > Taken apart advantages of keys, you get only bidrectional iteration,
which
> > is IMHO not interesting enough to justify adding a new data structure to
> > ExtLib.
[snip on arrays]

I think you should look at Brian proposal of IndexedTree (functionnal
array). It provides exactly that : a low cost insertion at any part of the
array. But any insertion/deletion will of course invalid the keys of some
parts of the array items. That's not exactly what you need here...

[snip on felix compilation]

I understand correctly your problem, because I got same when writing
compilers. It's often that you need several passes in order to optimize some
code or simply for example when writing a forward jump of N instructions
into a forward jump to address XX.
But I don't think dllist are the best solution here. As you said, you need
some rewriting rules, so what about :

instead of :

type opcode
type code = opcode array
type key = int (* index in the array *)

use :

type opcode
type code =
    | Op of opcode
    | Array of code array
type key = array * int (* pointer in the tree *)

you can then translate any part of your code into not only a single opcode
but into an array of opcodes, and they will remain correctly ordered. You
need a tree structure to perform rewriting rules correctly and efficiently ,
a dllist for this kind of problem is just an inconvenient way of handling
flat trees in a mutable fashion.

Nicolas