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

["Markus Weißmann" <markus.weissmann@in.tum.de>]

Taking one step back, what you actually want is a data structure that:

-is a container for elements of some type 'a
-some elements are tagged with a "state" tag 'b
-the elements have an ordering
-you can add elements
-you can tag elements with a "state" tag
-you can remove the current element
-you can remove the tag from the current element
-you can get the current element
-you can move the current element one step (forward&backward)
-you can get the tag of the current element
-you can move the current element one step to the next/prev tagged one

And you want this structure to be fast, right? Or do you only care about
the concrete implementation?
You should think about the type of the elements and tags you want to be
able to use: Do they have a natural ordering? Are they hashable?

I would advice you to 1st write the interface with the functions you
require, then think about the implementation. I'm under the impression
that you have a decent C implementation and want to transfer that to OCaml
at all costs.


Regards

-Markus

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

-- 
Markus Weißmann, M.Sc.
Institut für Informatik
Technische Universität München
Raum 03.07.054, Boltzmannstr. 3, 85748 Garching

mailto:markus.weissmann@in.tum.de