函數上需要實例聲明的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類型的上下文添加到所有的我定義使用我的設置類型，像這樣的功能，或者我得到一個錯誤類型：

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::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

您的實例聲明說那是什麼Set a是Eq實例每當a是。事實上，a實際上是否是Eq的實例完全是另一回事;這隻允許您將兩個Set與==進行比較，而在memberSet中，您只是比較元素。

考慮類型Integer -> Integer。這不是Eq的實例，原因很明顯。如果Set包含該類型的元素，您會如何期待memberSet工作？

我想知道你希望在這裏完成的是確保只有Set s與元素類型是Eq的實例可以創建。如果是這樣，這是一個非常不同的問題，但也大多是不必要的 - 使用Set s的功能限制Eq s最終達到相同的目的。

爲什麼不看看the standard Data.Set module？請注意，它在集合上運行的大多數函數都具有Ord約束，反映了使用的內部表示是二叉搜索樹的事實。

Answer 2

只是爲了好玩，你可以安排一下，這樣的限制是沒有必要的功能，通過使用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. 只要我們在Insert構造函數上進行模式匹配，就可以使用Eq上下文（和字典），所以我們不需要在函數的類型簽名中提及它。