Question about sets

Andrew J Bromage ajb@spamcop.net
Tue, 20 Aug 2002 14:13:52 +1000


G'day all.

On Tue, Aug 20, 2002 at 05:39:41AM +0200, Scott J. wrote:

> I have a question. Why are sets not implemented in Haskell? . I have read a
> bit how the compiler is made. Ok lists are easier to implement but sets
> could have been implemented too.
> So why didn't the implementors not do it?

Almost certainly because the most efficient implementation of sets
depends on data type and usage.  For many applications, binary trees
may be the most appropriate method.  For others, hash tables might be
better.  For others, dense bit vectors and for yet others, sorted
lists.

Of course Haskell could have defined signatures and some implementations
and left any specialist implementations up to the developer, however,
the "most correct" type signatures require fundeps, which are not in
Haskell 98.

Incidentally, if someone wants an interesting project, Edison hasn't
been touched in a while.  Getting it a) fundep-compliant, b) complete
and c) playing with the Monad Template Library would be a pretty
useful thing.

Cheers,
Andrew Bromage