[Haskell-beginners] what's a proper way to make a Set typeclass? and why is it not done already?

[Brent Yorgey]

On Tue, Jul 06, 2010 at 01:35:41AM +0300, Markus Läll wrote:
> I started like this:
> 
> {-# LANGUAGE
>    MultiParamTypeClasses,
>    FlexibleInstances #-}
> 
> import qualified Data.List as L
> 
> class (Eq e) => Set s e where
>    empty :: s e
>    fromList :: [e] -> s e
>    ...
> 
> ..and started to implement it on a list:
> 
> instance (Eq e) => Set [] e where
>    empty = []
>    fromList xs = L.nub xs
> 
> But I can't understand, why there has to be a (Eq a) context to the
> Set instance of a list, when the class definition seems to already say
> it? It won't compile without it..

The class definition says that an Eq constraint is *required*, it does
not provide it.  'instance Set [] e' would promise that the instance
will work for *any* type e (even ones without an Eq instance), but the
class declaration requires that e must have an Eq instance.  Hence the
error.

> Secondly, why do I need FlexibleInstances -- it gives me an eror which
> I don't understand ("all instance types must be of the form T a1 ...
> an" and so on, and recommends to add the flexible instances.)

The Haskell98 standard is quite convervative when it comes to the
sorts of instances you are allowed to declare.  I think in this case
it is complaining about the fact that e is a variable and not a
particular type constructor; I agree that particular error is rather
hard to decipher.  In any case, enabling FlexibleInstances is quite
common and harmless.

> Also I couldn't find other elaborate Set typeclasses -- there seems to
> be only the "Set a" type. Why is that(?), because you could use other
> datastructures, better and worse in various ways, than the balanced
> binary tree..

I guess for no better reason than because no one has ever wanted it.
Actually, another reason may be because it is a rather large design
space and no one has been able to agree on what such a type class
might look like.  But don't let either of those stop you.  

-Brent