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

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

[Goswin von Brederlow]

Hi,

I'm wondering if it is possible to implement greedy/inline data
structures in ocaml in a generic and reusable way.

Maybe you don't know what greedy/inline data structures are or maybe I'm
using the wrong name. So here is what I mean:

Say you have a task structure that is in 2 doubly linked list. One list
links all the structures together and the second list links structures
with the same internal state (running, sleeping, waiting, ...). In C you
would then have something like this:

struct task {
  DLIST(task, all);
  DLIST(task, state);
  foo_t data;
}

The DLIST makro adds the prev/next pointers to the struct, one set
prefixed with all, the other with state. There would also be makros to
to init, insert, remove and iterate of the two lists.

The internal pointer needed for the DLIST are part of the struct
task. The big advantage of this (and why I ask) is that given a task one
can esily remove it from both lists.

On the other hand if the list is external to the struct and only
contains a pointer to the task then removing a task becomes
difficult. The task then needs pointers to each of the lists data
structures creating cycles. Not good for ocaml. It also would waste
memory for 2 pointers (per list).



So how would you design such greedy/inline data structures in ocaml?

Or how else would you design containers (list, doubly linked list,
queue, ...) so that things can be in multiple containers and removing
them is fast?

MfG
        Goswin

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

[Edgar Friendly]

On 03/07/2012 09:41 AM, Goswin von Brederlow wrote:
> The task then needs pointers to each of the lists data
> structures creating cycles. Not good for ocaml. It also would waste
> memory for 2 pointers (per list).

Cycles are fine for ocaml, pointers are pretty cheap, and I think the 
answer to your question is no - there's a regularity to values that's 
required by the garbage collector, and what you seem to want is the 
ability to inline nested structures without pointers, and OCaml's data 
representation doesn't allow this, mainly because of the tag word needed 
by the GC.

Beware premature optimization.

E.

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

[Goswin von Brederlow]

Edgar Friendly <thelema314@gmail.com> writes:

> On 03/07/2012 09:41 AM, Goswin von Brederlow wrote:
>> The task then needs pointers to each of the lists data
>> structures creating cycles. Not good for ocaml. It also would waste
>> memory for 2 pointers (per list).
>
> Cycles are fine for ocaml, pointers are pretty cheap, and I think the
> answer to your question is no - there's a regularity to values that's
> required by the garbage collector, and what you seem to want is the
> ability to inline nested structures without pointers, and OCaml's data
> representation doesn't allow this, mainly because of the tag word
> needed by the GC.
>
> Beware premature optimization.
>
> E.

The problem with cycles is that you need to define all structures in a
cyled atomically as the same time. That means using "let rec foo =
... and bar = ..." and sometimes needing to lift function calls out of
the initialization.

For example and from memory you couldn't write this:

let rec task = {
    all_list = all_list;
    state_list = state_list;
    foo = bar;
}
and all_list = DList.create_item all_list_head task
and state_list DList.create_item state_list_head task

At the time the DList.create_item is called the task binding is still
incomplete and you get an error that it can't be on the right-hand side.

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.


Inlining the DList wihtout another indirection like in C would be nice
but would certainly require some camlp4 code to pull off. But it would
certainly be enough to pull in a pointer to the list structure as long
as you don't also need a back pointer inside the list structure. The
cycle is the problem there, just one direction is fine.

MfG
        Goswin

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

[Gabriel Scherer]

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

On Wed, Mar 7, 2012 at 5:32 PM, Goswin von Brederlow <goswin-v-b@web.de> wrote:
> Edgar Friendly <thelema314@gmail.com> writes:
>
>> On 03/07/2012 09:41 AM, Goswin von Brederlow wrote:
>>> The task then needs pointers to each of the lists data
>>> structures creating cycles. Not good for ocaml. It also would waste
>>> memory for 2 pointers (per list).
>>
>> Cycles are fine for ocaml, pointers are pretty cheap, and I think the
>> answer to your question is no - there's a regularity to values that's
>> required by the garbage collector, and what you seem to want is the
>> ability to inline nested structures without pointers, and OCaml's data
>> representation doesn't allow this, mainly because of the tag word
>> needed by the GC.
>>
>> Beware premature optimization.
>>
>> E.
>
> The problem with cycles is that you need to define all structures in a
> cyled atomically as the same time. That means using "let rec foo =
> ... and bar = ..." and sometimes needing to lift function calls out of
> the initialization.
>
> For example and from memory you couldn't write this:
>
> let rec task = {
>    all_list = all_list;
>    state_list = state_list;
>    foo = bar;
> }
> and all_list = DList.create_item all_list_head task
> and state_list DList.create_item state_list_head task
>
> At the time the DList.create_item is called the task binding is still
> incomplete and you get an error that it can't be on the right-hand side.
>
> 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.
>
>
> Inlining the DList wihtout another indirection like in C would be nice
> but would certainly require some camlp4 code to pull off. But it would
> certainly be enough to pull in a pointer to the list structure as long
> as you don't also need a back pointer inside the list structure. The
> cycle is the problem there, just one direction is fine.
>
> MfG
>        Goswin
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

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

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

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

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

[Gabriel Scherer]

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

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

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

[Goswin von Brederlow]

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

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

[Gabriel Scherer]

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

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

[Markus Weißmann]

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

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

[Goswin von Brederlow]

Markus Weißmann <markus.weissmann@in.tum.de> writes:

> 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

No, that was just the simplest example I could think of.

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

I want a set of standard containers that are combinable so that given an
element from any one of the containers it can be removed from all of
them efficiently. Efficient doesn't allways equal fast. What I don't
want is an operation that should be O(1) to suddenly take O(log n).

More generally given an element from any one of the containers all the
normal operation of any other container should be possible. All
containers should have a "remove this element" operation. Lists have a
"next". Double linked lists have "next" and "prev". Priority queue
should have "change priority". Queue might have "move to front" and
"move to back".

MfG
        Goswin

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

[Hezekiah M. Carty]

On Fri, Mar 9, 2012 at 4:21 AM, Gabriel Scherer
<gabriel.scherer@gmail.com> wrote:
> 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...
>
<useful code snippet removed>
>
> I think learning *not to use* fancy features is just as fun as using them.
>

To be fair, part of the process of learning when not to use fancy
features is using them, then discovering when these features made a
solution worse rather than better.  Polymorphic variants, the object
system, first class modules, GADTs - these all open up fun new ways to
approach problems.  They may not always be the 'best' tool for a
particular job, but not every implementation needs to be the 'best'.
When this learning and iteration process takes place on a public forum
other users get to learn from the experience as well.

With that said, suggestions for implementation simplifications are
important and fun to read too.

Hez

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

[Goswin von Brederlow]

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

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

[Gerd Stolpmann]

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

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

[Goswin von Brederlow]

Gerd Stolpmann <info@gerd-stolpmann.de> writes:

> 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

That is a start. But you used an open ended doubly linked list. This
makes it simpler because you can have an empty list and initialize items
to not be linked to anything before inserting them. That avoids the
cycles.

If you have a closed (cyclic or ring) doubly linked list the problem
becomes how to create the first element that must link to itself. Can
you come up with something without option type or Obj.magic? Something
that doesn't duplicate the initialization of the DList for each
instance.

MfG
        Goswin