Haskell type context from instance declaration required for functions

Question

I used the type context when creating the instance declaration for the data type I created.

data Set a = Insert a (Set a) | EmptySet instance (Show a) => Show (Set a) where show x = "{" ++ show' x ++ "}" where show' (Insert x EmptySet) = show x show' (Insert x xs) = show x ++ ", " ++ show' xs instance Eq a => Eq (Set a) where (Insert x xs) == (Insert y ys) = (x == y) && (xs == ys) 

So now I have to add an Eq type context to all the functions that I define that use my Set type, for example, or I get an error like:

 memberSet::Eq a =>a->Set a->Bool memberSet _ EmptySet = False memberSet x (Insert y ys) | x == y = True | otherwise = memberSet x ys subSet::Eq a=>Set a->Set a->Bool subSet EmptySet _ = True subSet (Insert a as) bs | memberSet a bs = subSet as bs | otherwise = False 

The error I get looks like this:

  No instance for (Eq a) arising from a use of `==' In the expression: (x == y) In a stmt of a pattern guard for an equation for `memberSet': (x == y) In an equation for `memberSet': memberSet x (Insert y ys) | (x == y) = True | otherwise = memberSet x ys Failed, modules loaded: none. 

What does it mean? Why am I getting this error? I realized that as soon as I make an instance declaration, Haskell will be able to automatically verify that things that compare with "==" in my memberSet and subSet functions will automatically check for Eq?

Edit for clarity:

My problem is that I do not understand why type contexts are needed for "memberSet" and "subSet". If I delete them like this, it will not compile.

  memberSet::a->Set a->Bool memberSet _ EmptySet = False memberSet x (Insert y ys) | x == y = True | otherwise = memberSet x ys subSet::Set a->Set a->Bool subSet EmptySet _ = True subSet (Insert a as) bs | memberSet a bs = subSet as bs | otherwise = False 

Answer 1

Your instance statement states that Set a is an instance of Eq when a is. Whether or not a is really, an instance of Eq is a completely different matter; it just allows you to compare two Set with == , and in memberSet you only compare elements.

Consider the type Integer -> Integer . This is not an example of Eq for reasons that should be obvious. How would you expect memberSet to work if Set contains elements of this type?

Interestingly, what you hoped to do here is to ensure that only Set with an element type can be instantiated with Eq . If this is so, then a completely different problem, but for the most part unnecessary, - leaving the Eq constraint on functions using Set , ultimately fulfills the same purpose.

Why not take a look at the standard Data.Set module ? Note that most of its functions that work with collections have an Ord constraint, reflecting the fact that the internal representation is used as a binary search tree.

Answer 2

Just for fun, you can arrange it so that restrictions are not needed for functions using GADT :

 {-# LANGUAGE GADTs #-} module Set where data Set x where EmptySet :: Set a Insert :: Eq a => a -> Set a -> Set a instance Show a => Show (Set a) where show EmptySet = "{}" show xs = "{" ++ show' xs ++ "}" where show' (Insert a EmptySet) = show a show' (Insert a ys) = show a ++ ", " ++ show' ys instance Eq (Set a) where (Insert x xs) == (Insert y ys) = x == y && xs == ys EmptySet == EmptySet = True _ == _ = False memberSet :: a -> Set a -> Bool memberSet x (Insert y ys) = x == y || memberSet x ys memberSet _ _ = False subSet :: Set a -> Set a -> Bool subSet EmptySet _ = True subSet (Insert a as) bs | memberSet a bs = subSet as bs | otherwise = False 

By placing an Eq constraint on an Insert type constructor, we can guarantee that

• It is not possible to build a nonempty collection for types outside of Eq .
• The Eq context (and dictionary) is available whenever we map the template to the Insert constructor, so we don’t need to mention it in the function type signature.