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

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

Hi,

I'm wondering if it is possible to implement greedy/inline data
structures in ocaml in a generic and reusable way.

Maybe you don't know what greedy/inline data structures are or maybe I'm
using the wrong name. So here is what I mean:

Say you have a task structure that is in 2 doubly linked list. One list
links all the structures together and the second list links structures
with the same internal state (running, sleeping, waiting, ...). In C you
would then have something like this:

struct task {
  DLIST(task, all);
  DLIST(task, state);
  foo_t data;
}

The DLIST makro adds the prev/next pointers to the struct, one set
prefixed with all, the other with state. There would also be makros to
to init, insert, remove and iterate of the two lists.

The internal pointer needed for the DLIST are part of the struct
task. The big advantage of this (and why I ask) is that given a task one
can esily remove it from both lists.

On the other hand if the list is external to the struct and only
contains a pointer to the task then removing a task becomes
difficult. 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).



So how would you design such greedy/inline data structures in ocaml?

Or how else would you design containers (list, doubly linked list,
queue, ...) so that things can be in multiple containers and removing
them is fast?

MfG
        Goswin