Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] Doubly-linked list
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2002-08-14 (08:16)
From: Diego Olivier Fernandez Pons <Diego-Olivier.FERNANDEZ-PONS@c...>
Subject: Re: [Caml-list] Doubly-linked list
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 Archives:
Bug reports: FAQ:
Beginner's list: