Haskell类型上下文来自函数所需的实例声明

Question

我在为我编写的数据类型执行实例声明时使用了类型上下文.

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)

所以现在,我必须将Eq类型上下文添加到我定义的所有使用我的Set类型的函数中,就像这样,或者我得到一个类型错误:

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

我得到的错误看起来像:

    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.

这甚至意味着什么？为什么我会收到此错误？我想,一旦我做了实例声明,Haskell就能自动验证在我的函数"memberSet"和"subSet"中被"=="比较的东西会自动被检查为"Eq？"的实例.

为清晰起见编辑:

我的问题是我不明白为什么在"memberSet"和"subSet"上需要类型上下文.如果我这样删除它们,它就不会编译.

  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

只是为了它的乐趣,你可以安排它,以便通过使用以下方法在函数上不需要约束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

通过将Eq约束放在Insert类型的构造函数上,我们可以确保

1. 对于不在的类型,不能构造非空集Eq.
2. Eq每当我们在Insert构造函数上进行模式匹配时,上下文(和字典)都可用,因此我们不需要在函数的类型签名中提及它.

Answer 2

你的实例声明说的是，这是每当是Set a的一个实例。事实上，是否是的一个实例完全是另一回事；这仅允许您将两个s 与进行比较，而 in则仅比较元素。EqaaEqSet==memberSet

考虑类型Integer -> Integer。这不是一个例子，Eq原因应该是显而易见的。如果包含该类型的元素，您期望如何memberSet工作？Set

我想知道您是否希望在这里完成的是确保只能创建具有Set作为 实例的元素类型的 s 。Eq如果是这样，那就是一个非常不同的问题，但也大多是不必要的——保留Eq对使用 s 的函数的约束Set最终达到相同的目的。

为什么不看看标准Data.Set模块呢？请注意，它的大多数对集合进行操作的函数都有一个Ord约束，反映了所使用的内部表示是二叉搜索树的事实。