From: Pierre Weis <weis@margaux>
Message-Id: <9305070731.AA19600@margaux.inria.fr>
Subject: Re: sets
To: xavier@Theory.Stanford.EDU (Xavier Leroy)
Date: Fri, 7 May 1993 09:31:51 +0200 (MET DST)
In-Reply-To: <9305061908.AA04126@Tamuz.Stanford.EDU> from "Xavier Leroy" at May 6, 93 12:08:25 pm
Xavier is right about set implementation using lists: the equality
problem is still there, as it is for trees. I skip on equality because
it is a ``generic'' problem for many other data structure in ML,
including lists (mem and memq) and association lists (assoc versus
assq). This problem is a real one and is not yet solved in ML.
I would like to precise that my preceding message is just some kind of
warning about the difficulty to implement set primitives, due to the
ML type system which forbids generic functions whose behaviour depends
on the type of their arguments.
> Similarly, I think
> generic sets implemented as balanced trees would also be tolerable in
> many situations.
Perfectly right. I think it's worth trying to get this
implementation, even if it is not as smart or as general as we could
imagine. I think your package is very useful, since it's a good
compromise between efficiency and generality, and I would be glad to
try and use it. So, Xavier, don't stop, go on coding for the Caml community!
I was just pointing out that, the same old story arose again with sets
as with lists or association, or I/Os, or printing, or equality, or
whatever needs to be a bit more clever than a good old (parametric)
polymorphic function.
Pierre Weis
----------------------------------------------------------------------------
Formel Project
INRIA, BP 105, F-78153 Le Chesnay Cedex (France)
E-mail: Pierre.Weis@inria.fr
Telephone: +33 1 39 63 55 98
----------------------------------------------------------------------------