English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Objective Caml release 3.08.2
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-11-25 (23:35)
From: skaller <skaller@u...>
Subject: Re: [Caml-list] Objective Caml release 3.08.2
On Fri, 2004-11-26 at 05:05, Frédéric Gava wrote:

> > and order matters for folds if the operator being folded
> > isn't associative.
> Ok. That's right. This is why I thinks, another fold is necessary for
> associative operators (and thus for possible optimizations of this fold) and
> thus wihtout side-effects.

Perhaps that should be a question: are there optimisations
which can be performed if the ordering constraint is dropped?

This probably has two parts:

(a) Is Set.min_elt as fast as Set.choose?
(b) Are there any other optimisations (eg deforestation) 
which would benefit?

I don't know the answer to either question in the particular
case of Set.

Perhaps there would be some benefit for a Set' data type,
which was unordered.

ISO C++ STL has an ordered Set type (which typically does use
a red black tree), and in Technical Report 1 (TR1), there
is an unordered set type, intended to be implemented with
a hash table.

So I would tend to think it may well be worthwhile adding
an unordered set to Ocaml. I guess some operations may
change from O(log N) to O(1), or from O(N log N) to just O(N),
eg fold.

John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net