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] Efficiency of 'a list
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2003-05-06 (13:29)
From: Diego Olivier Fernandez Pons <Diego-Olivier.FERNANDEZ-PONS@c...>
Subject: Re: [Caml-list] Two types of efficiency (Was Efficiency of 'a list)

On Mon, 5 May 2003, Eray Ozkural wrote:

> But it's almost certain that I will not write any functional
> structure library, ahem :P That's more like optimizing for an
> ensemble of data structures instead of 1 and I think it requires an
> expertise of its own.  Moreover, I don't want to be labeled "failed"
> :)

I did not meant to be rude and Chris Okasaki has made a very good job
promoting purely functional data structures and some important
theoretical work too.

In 1997 Roberto Tamassia and Luca Vismara wrote an article comparing
the design of GeomLib (the geometric package of JDSL) with the STL,
LEDA and CGAL, considering the following points :
- ease of use
- efficiency
- flexibility
- reliability
- extensibility
- reusability
- modularity
- functionality
- correctness checking

The only problem is that 6 years after that seminal paper, Geomlib is
still unreleased.

Okasaki made the same kind of mistake, writting the paper before the
library was ended ('Edison is still mostly a framework. That is, I
provide signatures, but not yet very many implementations. I indend to
populate this framework over the time, adding a new module every few

> What I have in mind is tight imperative code like:
> AVL Trees
> B+ Trees
> Disjoint Sets
> Some dynamic hash code
> PQ: Binary Heaps, etc. (I already did binary heap)
> k-d trees (I'm not sure if I wanna go into comp. geometry though ;) )

Structure monster should notice that :

(a) there are already many data structures (purely functional or
imperative) available in Caml. Structure monster should check the Caml
Hump (data structures section) or some pages I wrote on the subject

(b) there are already several projects of 'standard libraries',
including the official standard library for Caml. Structure monster
should not begin one more of this projects but join (or use the same
interface, design, naming conventions, ...) one of these.

        Diego Olivier

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: