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

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

Gabriel Scherer <gabriel.scherer@gmail.com> writes:

> 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

For the fun of it I wrote a version with first class modules. It is
pretty much like your inline solution with records of closures, just a
different syntax.

The one thing I can't eliminate is the code duplication for the
initialization. I'm starting to believe there is no way around using
Obj.magic or option types there. At least for the verry first task (in
each dlist). The right-hand restriction in a let rec simply prevents
putting that code into a function.

For DList the duplication is minimal because the container is so
simple. But for more complex container more code would have to be
duplicated. The code could be hidden behind camlp4 though.

MfG
        Goswin

----------------------------------------------------------------------

(* Type for doubly linked list *)
type 'a dlist = {
  mutable next : 'a;
  mutable prev : 'a;
}

(* Module to access a container in another type *)
module type Accessor = sig
  type a
  val get : a -> a dlist
end

(* create an access module from a closure *)
let make_accessor : 'a . ('a -> 'a dlist) ->
  (module Accessor with type a = 'a) =
  fun (type c) (fn : c -> c dlist) ->
    let module M = struct
      type a = c
      let get x = fn x
    end
    in
    (module M : Accessor with type a = c)

(* Iterator over a DList *)
let get_next : 'a . (module Accessor with type a = 'a) -> 'a -> 'a =
  fun (type a) x y ->
    let module D = (val x : Accessor with type a = a)
    in
    (D.get y).next

(* Now lets use this: *)

(* A task has 2 DList: all and state *)
type task = {
  all : task dlist;
  state : task dlist;
  name : string;
}

(* Accessors for the two DLists *)
let all = make_accessor (fun task -> task.all)
let state = make_accessor (fun task -> task.state)

(* Some sample tasks *)
let rec task1 = {
  all = { next = task2; prev = task2; };
  state = { next = task1; prev = task1; };
  name = "task1";
}
and task2 = {
  all = { next = task1; prev = task1; };
  state = { next = task2; prev = task2; };
  name = "task2";
}

let () =
  Printf.printf "all_next = %s, state_next = %s \n"
    (get_next all task1).name
    (get_next state task1).name