Haskell Type 함수에서 필요한 인스턴스 선언의 컨텍스트

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. 

이게 무슨 뜻입니까? 이 오류가 발생하는 이유는 무엇입니까? 인스턴스 선언을하면 하스켈은 내 함수 "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

는 a이 때마다 Set a이 Eq의 인스턴스 인 것입니다. 실제로 a이든 아니든간에 Eq의 인스턴스는 완전히 다른 문제입니다. 이 경우 두 개의 Set을 ==과 비교할 수 있으며 memberSet은 요소 만 비교하는 것입니다.

Integer -> Integer을 고려하십시오. 이는 분명해야하는 이유로 Eq의 인스턴스가 아닙니다. Set에 해당 유형의 요소가 포함되어 있다면 어떻게하면 memberSet이 작동하겠습니까?

여기에서 달성하고자하는 것이 Eq의 인스턴스 유형 인 Set 초를 만들 수 있는지 궁금합니다. 그렇다면, 이것은 매우 다른 문제이지만, 대부분 불필요합니다. 을 사용하는 함수에 Eq 제약 조건을 남기는 것은 결국 동일한 목적을 수행합니다.

the standard Data.Set module을 보시지 않겠습니까? 집합에서 작동하는 대부분의 함수는 Ord 제약 조건을 가지고 있으며 사용 된 내부 표현이 이진 탐색 트리라는 사실을 반영합니다.

Answer 2

제약이 GADT 사용하여 기능에 필요하지 않습니다 그래서 그것의 재미, 당신은 그것을 정렬 할 수 있습니다 단지에 대한 : 유형의 Insert 생성자에 Eq 제약 조건을 놓음으로써

{-# 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 

을 우리는 보장 할 수 있습니다

1. Eq에없는 유형에는 비어 있지 않은 세트를 만들 수 없습니다.
2. Eq 컨텍스트 (및 사전)는 Insert 생성자에서 패턴 일치 할 때마다 사용할 수 있으므로 함수의 유형 서명에서 언급하지 않아도됩니다.