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 NAA32399; Mon, 5 May 2003 13:57:49 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f 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 NAA00023 for ; Mon, 5 May 2003 13:57:48 +0200 (MET DST) Received: from harrier.mail.pas.earthlink.net (harrier.mail.pas.earthlink.net [207.217.120.12]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h45BvlT02747 for ; Mon, 5 May 2003 13:57:47 +0200 (MET DST) Received: from user-0cev2rh.cable.mindspring.com ([24.239.139.113] helo=[192.168.0.3]) by harrier.mail.pas.earthlink.net with esmtp (Exim 3.33 #1) id 19CebJ-0003EH-00 for caml-list@inria.fr; Mon, 05 May 2003 04:57:45 -0700 Subject: Re: [Caml-list] Two types of efficiency (Was Efficiency of 'a list) From: "Yaron M. Minsky" To: Caml List In-Reply-To: References: Content-Type: text/plain Organization: Cornell University Message-Id: <1052135863.2398.6046.camel@dragonfly.localdomain> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-5) Date: 05 May 2003 07:57:44 -0400 Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; yaron:01 minsky:01 yminsky:01 cornell:01 caml-list:01 api:01 pons:01 acyclic:01 thesis:01 bug:01 faq:01 beginner's:01 beginners:01 keyid:01 arrays:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk You're kidding, right? You're making a classic "best is enemy of the good" mistake here. Yes, there are lots of implementations, and it's not clear which of them is absolutely optimal. That doesn't mean ocaml shouldn't provide built-in support for one "good-enough" solution. Such support doesn't preclude using whatever the optimal algorithm is for the situation. But most of the time, it works fine, and having built in support improves the usability of the language greatly. I for one have never quite understood why the Set and Map modules only provide modular implementations, and why the API is relatively weak. My solution, and I'm sure that of many others, has been to write their own polymorphic set and map data structures. Luckly, ocaml makes that easy. But it seems clear to me that such data structures belong in the standard library. And some syntax support would be nice to have as part of this standard as well. y On Mon, 2003-05-05 at 03:31, Diego Olivier Fernandez Pons wrote: > You should not use a set of strings but a trie. There are of course a > lot of ways to implement tries : > > - trees of lists > - trees of arrays (or an optimized version with strings) > - ternary trees (balanced or not) > > You may even minimize your acyclic automaton using any of the > following algorithms : > - 2 phases algorithm (cf Dominique Revuz PhD thesis) > - Incremental minimization (Incremental construction of a minimal > acyclic finite state automata, Daciuk, Milhov, B. Watson, R. Watson, > Computer linguistics volume 26 number 1 mars 2000) > - minimization by Brzozowki's algorithm > - minimization by Hopcroft's algorithm > > For which one of these versions should Caml provide build-in support ? > > Diego Olivier > > ------------------- > 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 -- |--------/ Yaron M. Minsky \--------| |--------\ http://www.cs.cornell.edu/home/yminsky/ /--------| Open PGP --- KeyID B1FFD916 (new key as of Dec 4th) Fingerprint: 5BF6 83E1 0CE3 1043 95D8 F8D5 9F12 B3A9 B1FF D916 ------------------- 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