Re: Looking for a nail

From: Markus Mottl (
Date: Mon Jan 25 1999 - 21:37:40 MET

From: Markus Mottl <>
Message-Id: <>
Subject: Re: Looking for a nail
To: (Michel Schinz)
Date: Mon, 25 Jan 1999 21:37:40 +0100 (MET)
In-Reply-To: <> from "Michel Schinz" at Jan 25, 99 01:45:34 pm

> Here is a "big" suggestion: what I'd really like to see for OCaml is a
> good and consistent data structure library. The one shipped with OCaml
> is quite good, but there are some things I do not like about it:
> - some parts are "imperative" (Array, Hashtbl, ...), while others are
> "functional" (Set, Map, ...),

It would be nice if someone would extend Okasaki's implementation of
purely functional data structures. There are some really very efficient
implementations to be found there. Unfortunately, they are by far not
complete: the ADTs offer but the most basic functionality. So please
take a look at

and extend some of the modules of the port from SML to OCAML. If you
have something to contribute, just send it to me and I will put it on
my page. A very fine implementation of random access lists by Pierpaolo
Bernardi is already available...
In the meanwhile I will continue porting the last four chapters.

> - the interface of some of the modules are not as complete as one
> might wish (in almost all of my projects, I end up writing some
> basic functions, like list partitioning, ...),

I could also imagine some more functions that would be useful, e.g. with
sets (and maybe a small change in the implementation). I'll write a
separate mail on this...

> - none of the modules use the OO features of OCaml.

There is even a much more radical approach concerning OO:
Make all basic types classes! This would e.g. allow to put all kinds of
values into a list and iterate it with a print function - just one of
many other then possible things I miss...

I think this change could be done without breaking existing code. All
(most) standard functions on basic types would have to be changed. E.g.:

"print_string" could be something like:

  let print_string x = x # print_string

But preferably we would use functions like:

  let print x = x # print

and "x" could be any object having a "print" function. This would even
allow user-defined classes to be mixed with basic types in "general"
manipulation functions - as long as they have the appropriate interface...

I think that this proposition could greatly reduce the amount of low-level
tinkering with basic types.

Maybe we could try to test this with CAMLP4 - I think it wouldn't
be this difficult to transform sources with it in such a way that
expressions like:

  let x = 3


  let x = new int 3

where "int" is actually the class "int" (different name spaces!)

> 2. design two different versions of the library: one purely
> applicative, and the other one with in-place modification (note
> that these two versions could be different, because some data
> structures might not be efficient or interesting enough in the two
> versions; however, it would be great if the two designs were as
> similar as possible),

As Okasaki shows, most kinds of data structures can be implemented
in a very efficient and still purely applicative way. I am not sure
whether there are many data structures that deserve their existence in
both forms...

> 4. document them thoroughly (e.g., give the complexity of every
> function, ...).

Probably the biggest problem ;-)
Many people (including me) don't like writing documentation...

Best regards,

Markus Mottl,,

This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:18 MET