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

[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: 2003-05-05 (11:11) From: Mattias Waldau 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.

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

```