Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] Efficiency of 'a list
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Mattias Waldau <mattias.waldau@a...>
Subject: RE: [Caml-list] Two types of efficiency (Was Efficiency of 'a list)
> 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.



To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: