Re: [Caml-list] Doubly-linked list

[Brian Rogoff <bpr@artisan.com>]

Diego Olivier Fernandez Pons writes:
> Brian Rogoff a écrit
> > 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 
                          ^-constructor
> > 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) 

Yes, you can always map to modules, but I think overloading (or type
classes, if you want to distinguish from Ada and C++) are more convenient
for the user, but I suppose this is a well known disagreement that will
only be resolved by the proponents of the respective positions choosing
different languages. 

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

With OCaml 3.05 and above, you'll be able to use polymorphic methods to 
get non-uniform recursion. This issue has come up a lot on the list 
(see the archives) over the years and several proposals were made for 
adding this capability to the language. I don't know if adding this 
feature is a priority for the developers; it isn't clear that the data
structures in Okasaki's book constitute a strong enough argument for 
adding it. 

You may as well swipe the doubly linked list from the Cousineau/Mauny book
too. The library will be more useful if you're very careful about making
the interfaces very consistent, so that changing a data structure doesn't
cause much source code change. 
> 
> 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

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