From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id UAA12179; Mon, 5 May 2003 20:06:49 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id UAA11910 for ; Mon, 5 May 2003 20:06:47 +0200 (MET DST) Received: from eposta.kablonet.com.tr ([62.248.102.66]) by concorde.inria.fr (8.11.1/8.11.1) with SMTP id h45I6gH21808 for ; Mon, 5 May 2003 20:06:44 +0200 (MET DST) Received: (qmail 33260 invoked by uid 0); 5 May 2003 18:14:02 -0000 Received: from unknown (HELO 195.174.169.185) (exa@kablonet.com.tr@195.174.169.185) by 0 with SMTP; 5 May 2003 18:14:02 -0000 From: Eray Ozkural Reply-To: erayo@cs.bilkent.edu.tr Organization: Bilkent University CS Dept. To: Diego Olivier Fernandez Pons , "Yaron M. Minsky" Subject: Re: [Caml-list] Two types of efficiency (Was Efficiency of 'a list) Date: Mon, 5 May 2003 21:05:43 +0300 User-Agent: KMail/1.5.9 Cc: Caml List References: In-Reply-To: MIME-Version: 1.0 Content-Disposition: inline Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Message-Id: <200305052105.43350.exa@kablonet.com.tr> X-Spam: no; 0.00; eray:01 ozkural:01 caml-list:01 38,:01 pons:01 okasaki:01 ralf:01 hinze:01 baire:01 improvment:01 ahem:01 okasaki's:01 admittedly:01 hash:01 demons:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Monday 05 May 2003 19:38, Diego Olivier Fernandez Pons wrote: > Keep in mind that designing a data structure library is a hard work : > Chris Okasaki, Ralf Hinze and a lot of others have failed ; Baire has > not even been released after 1 year of work, the geometric algorithms > in JDSL (Java data structures library) never arrived and after 2 years > the new version 2.1 does not provide any real improvment over 2.0.6, > etc. > > The Caml standard library is in the 'not so bad' category Structure monster will help! (^_-) 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" :) But in the imperative area, I will consume algorithms one by one ;) I liked Okasaki's stuff btw, I even used those set thingies for a real quick hypergraph implementation (which was admittedly too slow for real life) 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 ;) ) So my clients will be speed demons who are not concerned with functional beauty of their basic data expressions. OTOH, I will demonstrate that imperative code can be elegant!!! I don't know, what else is left in the world? It's so easy to program in ocaml that I think I will do all of these and more this summer. (Complete with those pretty running time bounds) Assume I'm writing something like that, people don't want it to be functors but simply polymorphic types, is that so? While coding I had the impression that most of the data structures would fit into a functor-ful style. (same goes for haskell classes) Is these concerns because people are tired of the rather redundant means with which one is obliged to instantiate a data structure using functors? For instance if you're doing a priority queue, you want to know at least three things: 1) What is the type of key? 2) What is the type of record? 3) How do I compare them? Not too different from what Set module wants. I even had the wild idea of higher and higher level of abstractions but I don't know where those abstractions would start to bog down the code yet. As I said defining Set like the exactly mathematical way, and then defining implementation classes of sets, and then implementations will be the beginning that path of "i want more" kind of abstractions ;) And a good, in fact, very good thing about abstractions is that I can make a framework that can incorporate other people's code so that I won't have to write the whole world from scratch! I think that's a very nice idea since even I have a finite appetite for coding! I'm also right now developing a bad feeling that the "framework" design might be harder than it sounds... Cheers, -- Eray Ozkural (exa) Comp. Sci. Dept., Bilkent University, Ankara KDE Project: http://www.kde.org www: http://www.cs.bilkent.edu.tr/~erayo Malfunction: http://mp3.com/ariza GPG public key fingerprint: 360C 852F 88B0 A745 F31B EA0F 7C07 AE16 874D 539C ------------------- 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