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

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

Gerd Stolpmann <info@gerd-stolpmann.de> writes:

> Am Donnerstag, den 08.03.2012, 06:11 +0100 schrieb Goswin von Brederlow:
>> 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.
>
> There is a solution with functors. However, I don't dare to predict how
> fast it is (functors add additional indirection):
>
> module type DLINKABLE = sig
>   type t
>   val next : t -> t option
>   val prev : t -> t option
>   val set_next : t -> t option -> unit
>   val set_prev : t -> t option -> unit
> end
>
> module type DHEAD = sig
>   type dlist
>   type t
>   val first : dlist -> t option
>   val last : dlist -> t option
>   val set_first : dlist -> t option -> unit
>   val set_last : dlist -> t option -> unit
> end
>
> module DLIST(H : DHEAD)(L : DLINKABLE with type t = H.t) = struct
>   (* Here define operations over lists, e.g. *)
>
>   let remove (dl:H.dlist) (x:D.t) =
>     ( match D.prev x with
>         | None ->
>             H.set_first dl (D.next x)
>         | Some p ->
>             D.set_next (D.next x)
>     );
>     ( match D.next x with
>         | None ->
>             H.set_last dl (D.prev x)
>         | Some n ->
>             D.set_prev (D.prev x)
>     )
> end
>
> For a concrete application you would only have to implement DLINKABLE
> and DHEAD, and then apply DLIST on these implementations. If elements
> are members of several lists, do this for each list separately. I guess
> you could define macros for generating DLINKABLE and DHEAD (even the
> macros built into camlp4 could be good enough for this).
>
> Gerd

That is a start. But you used an open ended doubly linked list. This
makes it simpler because you can have an empty list and initialize items
to not be linked to anything before inserting them. That avoids the
cycles.

If you have a closed (cyclic or ring) doubly linked list the problem
becomes how to create the first element that must link to itself. Can
you come up with something without option type or Obj.magic? Something
that doesn't duplicate the initialization of the DList for each
instance.

MfG
        Goswin