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 NAA31535; Mon, 5 May 2003 13:11:28 +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 NAA31211 for ; Mon, 5 May 2003 13:11:27 +0200 (MET DST) X-SPAM-Warning: Sending machine is listed in blackholes.five-ten-sg.com Received: from mailg.telia.com (mailg.telia.com [194.22.194.26]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h45BBRT01006 for ; Mon, 5 May 2003 13:11:27 +0200 (MET DST) Received: from d1o849.telia.com (d1o849.telia.com [213.66.248.241]) by mailg.telia.com (8.12.9/8.12.9) with ESMTP id h45BBPu7013978; Mon, 5 May 2003 13:11:25 +0200 (CEST) X-Original-Recipient: caml-list@inria.fr Received: from gateway (h199n1fls34o849.telia.com [213.67.121.199]) by d1o849.telia.com (8.10.2p2/8.10.1) with ESMTP id h45BBOD27009; Mon, 5 May 2003 13:11:24 +0200 (CEST) From: "Mattias Waldau" To: "'Diego Olivier Fernandez Pons'" Cc: Subject: RE: [Caml-list] Two types of efficiency (Was Efficiency of 'a list) Date: Mon, 5 May 2003 13:11:22 +0200 Message-ID: <049301c312f7$12f58c10$0200a8c0@gateway> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.3416 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1165 Importance: Normal In-Reply-To: X-Spam: no; 0.00; mattias:01 waldau:01 caml-list:01 acyclic:01 thesis:01 prolog:01 iterated:01 arrays:01 ocaml:01 caml:01 lisp:01 sml:01 syntax:02 olivier:02 optimized:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > 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 > Hi Diego, yes, there are many datastructures to choose from, and all have their advantages. Of course, a built-in support solution will not be optimal, but it will definitely be better than a unordered list of strings :-) As a programming language designer, you tell the users the preferred way to do things, and for example almost all pure languages that has been born on a university (LISP, Prolog, SML, Ocaml, ....) use lists as a primary datastructure. I have never understood this love of list, since the only efficient use of a list is as a stack which can be iterated over. Prolog have a little advantage where append is an O(1)-operation instead of an O(n), however searching is still O(n). It would be interesting to see how a typed scripting language (maybe built on top of ocaml) with advanced built-in datastructures (with syntax support) would look like. Cheers, Mattias ------------------- 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