Haskell Type Context from instance declaration required on functions

Question

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

Answer 1

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

1. No nonempty set can be constructed for types not in Eq.
2. 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.

Answer 2

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.