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

Sure. I think you missed the "For the fun of it" right at the begining.

One advantage of using a first class module though is that they are
extensible. I could define 2 accessor modules:

    let module DList_Accessor = struct
      type a = c
      let get_next x = get_next x.dlist
      let get_prev x = get_prev x.dlist
      let set_next x = set_next x.dlist
      let set_prev x = set_prev x.dlist
    end

    let module PrioQueue_Accessor = struct
      type a = c
      let get_next x = get_next x.queue
      let get_prev x = get_prev x.queue
      let set_next x = set_next x.queue
      let set_prev x = set_prev x.queue
      let get_prio x = get_prio x.queue
      let set_prio x = set_prio x.queue
    end

Now any function that operates on (module DList) can also be called with
(module PrioQueue). You can't do that with closures or records of
closures. You can do it with objects though.

Note: you probably wouldn't implement a priotity queue as doubly linked
list. Just an example.

> 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

MfG
        Goswin