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

["Yaron M. Minsky" <yminsky@CS.Cornell.EDU>]

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