# Haskell Type Context from instance declaration required on functions

I used a type context in doing an instance declaration for a data type I made up.

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 the Eq type context to all of the functions I define that use my Set type, like so, or I get a type error:

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:

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 this even mean? Why do I get this error? I figured that once I did the instance declaration, Haskell would be able to automatically verify that the things being compared by "==" in my functions "memberSet" and "subSet" would automatically be checked to be instances of "Eq?"

Edit for clarity:

My issue is that I don't understand why the type contexts are necessary on "memberSet" and "subSet." If I remove them like so, it doesn't 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

## Answers

What your instance declaration says is that Set a is an instance of Eq whenever a is. Whether or not a is, in fact, an instance of Eq is another matter entirely; this merely allows you to compare two Sets with ==, while in memberSet you're only comparing elements.

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

I wonder if what you were hoping to accomplish here is ensuring that only Sets with an element type that's an instance of Eq can be created. If so, that's a very different problem, but also mostly unnecessary--leaving the Eq constraint on the functions using Sets serves the same purpose in the end.

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

Just for the fun of it, you can arrange it so that the constraints aren't necessary on the functions by using a 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 putting the Eq constraint on the Insert constructor of the type, we can ensure that

- No nonempty set can be constructed for types not in Eq.
- The Eq context (and dictionary) is available whenever we pattern-match on the Insert constructor, so we don't need to mention it in the function's type signature.