Re: [Caml-list] Doubly-linked list

[Brian Rogoff <bpr@artisan.com>]

Diego Olivier Fernandez Pons writes:
> Oleg a écrit :
> 
> > P.S. BTW, one could have identical interfaces for a) resizable arrays, b) 
> > doubly-linked lists and c) deques, the only difference being the efficiency 
> > of various operations. It could be convenient for a programmer, because final 
> > data representation can be chosen after the program has been profiled and 
> > without changing much code. Has anyone tackled this problem?
> 
> I will be soon releasing a data structure library (september) which
> includes a port of EDiSon (GHC/hslibs/data/Edison in the GHC CVS), all
> data structures that were in Okasaki's purely functional data
> structures book and some more (weight balanced trees, cartesian trees,
> priority search queues, ...)

I'm looking forward to seeing it. I get the impression that Edison uses 
(multi-parameter) type classes so it isn't clear that it will translate 
well. Oh yeah, I may as well add my biannual plea for some form of
overloading in OCaml, which is somewhere in the top 3 of my wishlist. 

Anyways, doubly linked lists are a textbook example of an imperative data 
structure, and, waddya know, a very good textbook (the Cousineau/Mauny one
which is owned by everyone on this list ;-) has this example pretty early
in the section on imperative programming. Look here for the source 

http://pauillac.inria.fr/cousineau-mauny/main.html

but realize that you'll have to translate the source into OCaml. If I
remember correctly, the doubly linked list looks something like 

type 'a t = 
  { data : 'a; 
    mutable prev : 'a t; 
    mutable next : 'a t
  }

let create e = let rec x = {data = e; prev = x; next = x} in x

etc. 

which is very nice if you are used to trying such things in SML. 

-- Brian
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners