RE: [Caml-list] Two types of efficiency (Was Efficiency of 'a list)

["Mattias Waldau" <mattias.waldau@abc.se>]

> 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