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

[Ville-Pertti Keinonen <will@exomi.com>]

On Sunday, May 4, 2003, at 09:46 Europe/Helsinki, Mattias Waldau wrote:

> We are talking about two kinds of efficiency:
> 1. Absolute speed for mostly small benchmarks
> 2. Scalable programs, i.e. they work fine for input of length 100,
>    but goes on forever for input of length 1000.

No.  What you suggested (replace lists with sets, replace arrays with 
maps) would in many places be trading O(1) behavior for O(log n) 
behavior, which certainly doesn't make programs more scalable.

> It would be nice if the typechecker could deduce the type of the set 
> and
> add the above declaration automatically to the program. That would make
> it easier for beginners to use the advanced datastructures of Ocaml.

Implementing 'a set and ('a, 'b) map types in OCaml is trivial; in the 
OCaml library, for some reason ('a, 'b) Hashtbl.t is available but Set 
and Map are only provided through functors.

-------------------
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