From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA28364 for caml-redistribution; Tue, 26 Jan 1999 18:40:46 +0100 (MET) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id VAA30023 for ; Mon, 25 Jan 1999 21:37:59 +0100 (MET) Received: from miss.wu-wien.ac.at (miss.wu-wien.ac.at [137.208.107.17]) by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id VAA02844 for ; Mon, 25 Jan 1999 21:37:58 +0100 (MET) Received: (from mottl@localhost) by miss.wu-wien.ac.at (8.9.0/8.9.0) id VAA22593; Mon, 25 Jan 1999 21:37:40 +0100 (MET) From: Markus Mottl Message-Id: <199901252037.VAA22593@miss.wu-wien.ac.at> Subject: Re: Looking for a nail To: michel.schinz@csem.ch (Michel Schinz) Date: Mon, 25 Jan 1999 21:37:40 +0100 (MET) Cc: caml-list@inria.fr (OCAML) In-Reply-To: from "Michel Schinz" at Jan 25, 99 01:45:34 pm X-Mailer: ELM [version 2.4 PL21] MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit Sender: weis > 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 http://miss.wu-wien.ac.at/~mottl/ocaml_sources 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 become 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 -- Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl