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 (12:48)
From: Eray Ozkural <exa@k...>
Subject: Re: [Caml-list] Two types of efficiency (Was Efficiency of 'a list)
On Sunday 04 May 2003 09:46, Mattias Waldau wrote:
> 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.

Nice in theory but doesn't really alleviate the problem.


Because a novice can always shoot himself in the foot. Overuse of any 
datastructure is overkill. If I use the cumbersome R-B trees everywhere, it 
will not guarantee my program to be efficient.

Somebody who doesn't understand asymptotic complexity will use things like a 
map from strings to strings. You almost never use strings as keys in a tree. 
You use tries or trie hashing, etc. In KDE source code, for instance, I've 
seen a lot of instances of such lousy data structures...

Just to point out that there is no such thing as the ultimate index structure 
that works with any kind of key and any kind of records.

Therefore attaching syntactic significance to one particular data structure 
might be highly confusing for programmers. I don't recommend it.

What I would recommend would be a more abstract way of doing the same thing.

let A = { 3, 5, 7 }

It does look like such a statement has its merits! But yet, one must 
explicitly state what kind of a data structure he really wants somehow. Maybe

let A = { 3, 5, 7 } : MyCuteSet

BTW, a really abstract set data type does *not* assume a total ordering among 
elements. That's because I might want to implement multi-sets as unordered 
lists! Those kinds of things depend on the application. I really don't know 
how one would solve this in a static syntaxed language! 


Eray Ozkural (exa) <>
Comp. Sci. Dept., Bilkent University, Ankara  KDE Project:
www:  Malfunction:
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: