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