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) 

はだから今、私は私はそうのように、私のセットタイプを使用して定義するか、私は型エラーを取得する機能のすべてに、式のタイプのコンテキストを追加する必要があります。

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」と上必要である理由を私は理解していないということである「サブセット」私がそれらを削除すると、コンパイルされません。あなたのインスタンス宣言が言う

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

はaがあるたびSet aがEqのインスタンスであるということです。 aが実際にはEqのインスタンスであるかどうかはまったく別の問題です。これは2つのSetを==と比較するだけで、memberSetでは要素を比較しているだけです。

Integer -> Integerとします。理由は明らかであるため、これはEqのインスタンスではありません。 Setにそのタイプの要素が含まれていると、どのようにしてmemberSetが動作すると思いますか？

ここで達成しようとしていたのは、Eqというインスタンスの要素タイプのSetだけを作成できることでしょうか。そうであれば、それは非常に異なる問題ですが、ほとんどの場合は不要です。Eqの制約をSetを使用する関数に残すことは、最後に同じ目的を果たします。

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 

タイプのInsertコンストラクタにEq制約を置くことによっては、

1. Eq以外のタイプの場合、空でないセットは作成できません。
2. Eqコンテキスト（および辞書）は、Insertコンストラクタでパターンマッチするたびに使用できます。そのため、関数の型シグネチャでは言及する必要はありません。