Re: [Caml-list] Can one implement greedy/inline data structures in ocaml?

[Goswin von Brederlow <goswin-v-b@web.de>]

Edgar Friendly <thelema314@gmail.com> writes:

> On 03/07/2012 09:41 AM, Goswin von Brederlow wrote:
>> The task then needs pointers to each of the lists data
>> structures creating cycles. Not good for ocaml. It also would waste
>> memory for 2 pointers (per list).
>
> Cycles are fine for ocaml, pointers are pretty cheap, and I think the
> answer to your question is no - there's a regularity to values that's
> required by the garbage collector, and what you seem to want is the
> ability to inline nested structures without pointers, and OCaml's data
> representation doesn't allow this, mainly because of the tag word
> needed by the GC.
>
> Beware premature optimization.
>
> E.

The problem with cycles is that you need to define all structures in a
cyled atomically as the same time. That means using "let rec foo =
... and bar = ..." and sometimes needing to lift function calls out of
the initialization.

For example and from memory you couldn't write this:

let rec task = {
    all_list = all_list;
    state_list = state_list;
    foo = bar;
}
and all_list = DList.create_item all_list_head task
and state_list DList.create_item state_list_head task

At the time the DList.create_item is called the task binding is still
incomplete and you get an error that it can't be on the right-hand side.

So then you need mutable option types or mutables that you initialize
with dummy values and then overwrite with the real thing once all
members of a cycle are created. Or some other trickery to make it
work. Overall cycles are generally not good.


Inlining the DList wihtout another indirection like in C would be nice
but would certainly require some camlp4 code to pull off. But it would
certainly be enough to pull in a pointer to the list structure as long
as you don't also need a back pointer inside the list structure. The
cycle is the problem there, just one direction is fine.

MfG
        Goswin