Hello,
In my recent attempt to convert somebody from that (tm) language to
Haskell, I ran into a few problems when it came to the Set module
provided with ghc.
The problem, I think, stems from the need for *efficient implementation*
which has unfortunately totally destroyed the abstraction.
[a]
The first problem is that we need have an order on the elements:
> data Fu = Bloop Int -- deriving (Eq,Ord)
> f = mkSet [ Bloop a | a <- [1..10] ]
will not work. We need the deriving clause. Of course, Equality is needed,
one cannot check for duplicates otherwise. But Ord? I suspect this is only
needed because the Sets are unfortunately implemented with FiniteMaps (which in
turn needs Ord). The notion of Set doesn't require the notion that one should
be able to order the elements, so this notion is destroyed in the
implementation.
[b]
The second problem occured because the user wanted a set of sets.
> bloo = mkSet [ (f,10) ]
This means that we unfortunately need an order on the elements, which turn out
to be Sets.
The user instantly tries:
> instance Ord (Set a) where
> blah blah
which doesn't work because it turns out that Set is not a data type but
a type synonym. So, the user has to go and learn about FiniteMaps, and
write something like:
> instance (Eq a, Eq b) => Eq (FiniteMap a b) where
> x == y = fmToList x == fmToList y
> instance (Ord a, Ord b) => Ord (FiniteMap a b) where
> x <= y = fmToList x <= fmToList y
In short, I think that the notion of Set as implemented in ghc is broken.
The concept of a set has been destroyed by the chosen implementation.
It is of course probably a lot more difficult to implement a set efficiently
without requiring order, but then it will indeed be a set. I propose solving
this dilemma by renaming the set module. They aren't sets, they are special
types of sets.
Comments?
Jon
-------------------------------------------------------------
Jon Mountjoy - [EMAIL PROTECTED] - http://carol.fwi.uva.nl/~jon/
