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: 2003-05-04 (07:43)
From: Ville-Pertti Keinonen <will@e...>
Subject: Re: [Caml-list] Two types of efficiency (Was Efficiency of 'a list)

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 Archives:
Bug reports: FAQ:
Beginner's list: