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

[Gabriel Scherer <gabriel.scherer@gmail.com>]

I have implemented a small example in two versions: one with external
dllist (I'm using the Batteries Dllist module), which indeed needs a
small hack to bootstrap a single-element cycle, and one with inline
pointers as you show, using simple value recursion. In the second case
I also have a small abstraction layer for traversals -- only
instantiated in the 'iter' case currently -- that could save some code
duplication; that must be one of the "closures" tricks you were
thinking of, but I don't claim that it's as efficient than duplicated
specialized traversal functions.

The code is here:
  https://gitorious.org/gasche-snippets/outside-or-inline-lists/blobs/master/goswin_dllists.ml

On Thu, Mar 8, 2012 at 6:11 AM, Goswin von Brederlow <goswin-v-b@web.de> wrote:
> Gabriel Scherer <gabriel.scherer@gmail.com> writes:
>
>>> 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.
>>
>> I believe the trick you need (either passing a dummy value of your
>> type, or Obj.magic) is less ugly that your Camlp4 solution for inline
>> access.
>> If I really needed absolute performance, I'd use the inline version
>> just like in C, with mutable fields, but without preprocessor sugar.
>> Preprocessing could avoid a bit of duplication (corresponding to
>> manual inlining) on the structure-definition side, but wouldn't
>> simplify the structure-using code much.
>
> How?
>
> type task = {
>     mutable all_next : task;
>     mutable all_prev : task;
>     mutable state_next : task;
>     mutable state_prev : tast;
>     ...
> }
>
> Now how do yout write DList.insert, DList.remove, DList.iter, ...?
>
> I'm looking for some nice tricks using closures, functors, first class
> modules or something to make it look pretty and easy to use.
>
> I do have an ugly solution but I'm hoping for some fresh idea not based
> on what I already know is ugly. I can't be the only one that found the
> need to keep an item in two containers and be able to remove it from
> both quickly, right?
>
> MfG
>        Goswin