Haskell Tipo Contexto de declaración de instancia requerida en las funciones

Question

Utilicé un contexto de tipo al hacer una declaración de instancia para un tipo de datos que hice.

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) 

Así que ahora, tengo que añadir el contexto tipo de ecuación a todas las funciones que definen esa utiliza mi tipo de lance, como tal, o me sale un error de tipo:

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 

El error Obtengo mi apariencia como:

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. 

¿Qué significa esto? ¿Por qué obtengo este error? Pensé que una vez que hice la declaración de la instancia, Haskell podría verificar automáticamente que las cosas que se comparan por "==" en mis funciones "memberSet" y "subSet" se verificaran automáticamente como instancias de "Eq?"

Editar para mayor claridad:

Mi problema es que no entiendo por qué los contextos tipo son necesarios en "MemberSet" y "subconjunto". Si los elimino así, no compila.

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

lo que dice su declaración de instancia es que Set a es una instancia de Eq siempre es a. Si o no a es, de hecho, una instancia de Eq es completamente otra cuestión; esto simplemente le permite comparar dos Set s con ==, mientras que en memberSet solo está comparando elementos.

Considere el tipo Integer -> Integer. Esta no es una instancia de Eq por razones que deberían ser obvias. ¿Cómo esperaría que memberSet funcione si el Set contiene elementos de ese tipo?

Me pregunto si lo que esperaba lograr aquí es garantizar que solo Set s con un tipo de elemento que es una instancia de Eq se pueda crear. Si es así, ese es un problema muy diferente, pero también innecesario: dejar la restricción Eq en las funciones usando Set s tiene el mismo propósito al final.

¿Por qué no echar un vistazo a the standard Data.Set module? Tenga en cuenta que la mayoría de sus funciones que operan en conjuntos tienen una restricción de Ord, lo que refleja el hecho de que la representación interna utilizada es un árbol de búsqueda binario.

Answer 2

Sólo por el gusto de hacerlo, se puede organizar de tal manera que las limitaciones no son necesarios en las funciones mediante el uso de un 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 

Al poner la restricción en el EqInsert constructor del tipo , podemos asegurarnos de que

1. Ningún conjunto no vacío se puede construir para los tipos no en Eq.
2. El contexto Eq (y el diccionario) está disponible cada vez que ajustamos el patrón en el constructor Insert, por lo que no es necesario mencionarlo en la firma de tipo de la función.