Re: [Caml-list] Doubly-linked list

[Diego Olivier Fernandez Pons <Diego-Olivier.FERNANDEZ-PONS@cicrp.jussieu.fr>]

Brian Rogoff a écrit

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

I had to make many changes to Edison's structure including :

- flattening the Haskell class hierarchy
  Edison has Coll, XColl, OrdColl, Set, XSet, OrdSet ... you can see a
  few diagrammas (in fact lattices) in Okasaki's overviews of Edison.
  They have been all reduced into 4 types (Sequences, Collections,
  Sets and Maps) in various flavors (polymorphic, functor, in place)

- transforming some lazy data structures to strict (and providing
  functors and various flavors of streams for those who want amortized
  data structures via lazy evaluation)

- eliminating data structures that could not be translated to Caml,
  which includes some multi-parameter classes (that was not the most
  difficult part in fact) and non-uniform recursion (most of the last
  3 chapters of Okasaki's book, Markus Mottle had the same problem
  with his translation to Caml)

There won't be much new if you already use Markus Mottle port :
- weight balanced trees (Stephen Adams 1992)
- cartesian trees (Jean Vuillemin 1980)
- catenable (functional) lists (Chris Okasaki 1998)
- chromatic trees (Sabine Hanke 1997)
- priority search queues (Ralph Hinze 2001)
- various flavors of streams
- some mutable lists
- I have also completed Pottier's simply linked circular lists


        Diego Olivier

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