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

[Gerd Stolpmann <info@gerd-stolpmann.de>]

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



> 
> 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
> 

-- 
------------------------------------------------------------
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
Creator of GODI and camlcity.org.
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
*** Searching for new projects! Need consulting for system
*** programming in Ocaml? Gerd Stolpmann can help you.
------------------------------------------------------------