ocaml-lib-devel

[Ocaml-lib-devel] Enum, doubly linked lists, and thoughts

[Brian H. <bh...@sp...>]

I'm playing (while waiting for compiles) at writting a circular, mutable,
doubly linked list data structure.  The advantage of this is that inserts
anywhere into the list are O(1), if you have a pointer into the list.

Enum is almost a perfect vehicle for this- internal to the enum I'm 
keeping a reference to the current element.  If I could just 'reach into' 
the enum and snag this reference, all would be good with the world.  But I 
can't figure out how to do that (this may be because it's friday afternoon 
of a long, stressfull week and my brain is mush).

So this leaves me with three options, that I wanted to throw out to the 
listmind at large for input:

1) I can extend Enum to do what I want/need.  Nicolas is probably against 
this.  And here I think I actually agree with him- we don't want to extend 
Enum in ways that make it hard/inefficient/impossible to apply to native 
linked lists.

2) I can implement a whole new interface, call it Pointer for lack of a 
better name, and implement *that*.  One member of this interface being 
Pointer.enum_of, an O(1) creation of an enumeration given a pointer.

3) I can just add the pointer library, without any generalization (but
still with the enum_of function), to the Dllist library.

Thoughts?

Brian

Re: [Ocaml-lib-devel] Enum, doubly linked lists, and thoughts

[Nicolas C. <war...@fr...>]

> I'm playing (while waiting for compiles) at writting a circular, mutable,
> doubly linked list data structure.  The advantage of this is that inserts
> anywhere into the list are O(1), if you have a pointer into the list.
>
> Enum is almost a perfect vehicle for this- internal to the enum I'm
> keeping a reference to the current element.  If I could just 'reach into'
> the enum and snag this reference, all would be good with the world.  But I
> can't figure out how to do that (this may be because it's friday afternoon
> of a long, stressfull week and my brain is mush).

With circular lists, your next() function will of course never raise
No_more_elements, and count() should also be something like :
let rec infinite_count() = infinite_count()
And doing an *.of_enum with a cicular list will of course run until you kill
the process or run out of memory, same for Enum.iter... You could hack
something like waiting for physical equality with the first element to break
the loop, but if there is a map done before, you will never get it ! Enums
are right know (and should remain) enumerations on finite set of elements, I
don't really see how you could use them with an infinite set... So once you
get your Enum from a circular list, how are you supposed to use it ? (
remember that next() is hidden ! ) I suggest then that you write a different
module, having an of_enum function that will create an list and make it
circular but no enum function since such Enum cannot be used later :-)

Nicolas Cannasse

Re: [Ocaml-lib-devel] Enum, doubly linked lists, and thoughts

[Brian H. <bri...@ql...>]

On Wed, 30 Apr 2003, Nicolas Cannasse wrote:

> > I'm playing (while waiting for compiles) at writting a circular, mutable,
> > doubly linked list data structure.  The advantage of this is that inserts
> > anywhere into the list are O(1), if you have a pointer into the list.
> >
> > Enum is almost a perfect vehicle for this- internal to the enum I'm
> > keeping a reference to the current element.  If I could just 'reach into'
> > the enum and snag this reference, all would be good with the world.  But I
> > can't figure out how to do that (this may be because it's friday afternoon
> > of a long, stressfull week and my brain is mush).
> 
> With circular lists, your next() function will of course never raise
> No_more_elements, and count() should also be something like :
> let rec infinite_count() = infinite_count()
> And doing an *.of_enum with a cicular list will of course run until you kill
> the process or run out of memory, same for Enum.iter... You could hack
> something like waiting for physical equality with the first element to break
> the loop, but if there is a map done before, you will never get it ! 

Sorry, I wasn't clear.  It's internal structure is circular so that I
don't have to define a NULL.  But externally it will be a finite list, and
have a most definate end and begining.  This circularness will be hidden 
internally.

Here's the basic idea I have so far and some example functions:

type 'a dllist_elem_t = { datum : 'a; mutable next : 'a dllist_elem_t;
                          mutable prev : 'a dllist_elem_t }

type 'a dllist_head_t = Empty | NotEmpty of 'a dllist_elem_t

type 'a dllist_t = 'a dllist_head_t ref

let head dllist =
    match !dllist with
        Empty -> assert false (* or something *)
        | NotEmpty head -> head.datum

let prepend dllist x =
    let rec newelem = { datum = x ; next = newelem ; prev = newelem } in
    match !dllist with
        Empty -> dllist := (NotEmpty newelem)
        | NotEmpty head ->
		newelem.next <- head;
                newelem.prev <- head.prev;
                head.prev <- newelem;
                newelem.prev.next <- newelem;
                dllist := NotEmpty(newelem)


let count dllist =
    match !dllist with
        Empty -> 0
        | NotEmpty head ->
            let tail = head.prev in
            let rec loop elem cnt =
                if elem == tail then (cnt + 1) else
                loop (elem.next) (cnt + 1)
            in
            loop head 0


let iter f dllist =
    match !dllist with
        Empty -> ()
        | NotEmpty head ->
            let tail = head.prev in
            let rec loop elem =
                f elem;
                if (elem == tail) then () else loop elem.next
            in
            loop head



Notice in head- I don't return the dllist_elem_t, I return the element in 
it.  This is how I want it to work- dllist_elem_t never "leaks" out of the 
internal representation.  Also note that although I have a double 
dereference to get to the first element (the reference and the enumerated 
type) after that everything else is just 1 reference away.  

But this actually raises problems with doing a pointer type external from 
the linked list.  I suppose what I want is sort of an OO interface, with a 
"protected" inteface seen only inside the module, and a "public" interface 
I can put into the .mli and everyone can use.  But I'm not 100% sure how 
to do this.

Brian