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

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

I think this is a case of using a fancy new construction when a
simpler construction would do just as well.
For some reasons some people, even beginners, are absolutely fond of
first-class modules, and insist on using them in situation where
they're really not needed. I not eager to see what they will do with
GADTs...

In your case, you could simply use ('a -> 'a dllist) instead of your
Accessor module. Your code works just fine with the following
definitions of make_accessor and get_next:

  let make_accessor f = f (* useless, for code compatibility *)
  let get_next get y = (get y).next

I think learning *not to use* fancy features is just as fun as using them.

On Fri, Mar 9, 2012 at 8:50 AM, Goswin von Brederlow <goswin-v-b@web.de> wrote:
> 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