来自函数所需实例声明的 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 的约束类型的构造函数，我们可以确保

不能为不在 Eq 中的类型构造非空集.

Eq只要我们在 Insert 上进行模式匹配，上下文(和字典)就可用。构造函数，所以我们不需要在函数的类型签名中提及它。