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