Типы Алгебраические данных и равенство

Question

Учитывая следующие типы данных из TypeClassopedia:

data Cons a = Cons a (Cons a) | Empty deriving (Show, Eq)

Я осуществил свою злую реализацию Functor:

instance Functor Cons where 
    fmap _ Empty  = Empty 
    fmap f (Cons x xs) = Cons (f x) (Cons (f x) (fmap f xs)) 

Затем я попытался написать функцию (QuickCheck недвижимость), который принимает Cons a и возвращает Bool:

prop_id_functor_law :: Cons a -> Bool 
prop_id_functor_law x = fmap id x == id x 

Однако я получаю ошибку компиляции:

Prelude> :l EvilFunctor 
[1 of 1] Compiling EvilFunctor  (EvilFunctor.hs, interpreted) 

EvilFunctor.hs:18:23: 
    No instance for (Eq a) arising from a use of `==' 
    Possible fix: 
     add (Eq a) to the context of 
     the type signature for prop_id :: Cons a -> Bool 
    In the expression: fmap id x == id x 
    In an equation for `prop_id': prop_id x = fmap id x == id x 
Failed, modules loaded: none. 

Моей грубая интуиции, что это ошибка времени компиляции имеет смысл. Как можно сравнить два a, если они не использовали Eq?

Однако, что сделал deriving ... Eq, даже если я определил data Cons a?

Answer 1

В нем говорится, что вам необходимо добавить ограничение на prop_id_functor_law, так что это будет prop_id_functor_law :: Eq a => Cons a -> Bool. deriving часть просто означает, что он получает экземпляр

instance Eq a => Eq (Cons a) where 
    Empty == Empty = True 
    Cons a1 x1 == Cons a2 x2 = a1 == a2 && x1 == x2 
    _ == _ = False 

У вас еще есть, что параметр типа ограничен для того, чтобы, например Eq быть удовлетворены. Если вы проверили :info Cons в GHCi, вы увидите этот экземпляр.

Answer 2

what did the deriving ... Eq even do when I defined data Cons a ?

Когда вы извлечь экземпляр, GHC всегда механически создает экземпляр, который реализует логику, необходимую классом типа для структуры типа. Например:

data Foo = Foo Int Int 
    deriving Eq 

Даст вам что-то вроде:

instance Eq Foo 
    where Foo a b == Foo a' b' 
      = a == a' && b == b' 

Но если бы вы вместо этого:

data Foo a b = Foo a b 
    deriving Eq 

Тогда можно сказать, что это должно следовать той же структуры (Foo с равны, если оба содержащихся поля равны), но он вынужден делегировать равенство для типов a и b для части сравнения. Это не всегда типов, которые имеют равенство, поэтому полученный экземпляр должен заявить, что они делают, как ограничения:

instance (Eq a, Eq b) => Eq (Foo a b) 
    where Foo a b == Foo a' b' 
      = a == a' && b == b' 

То же самое происходит и для Cons. Поэтому два значения Cons a сопоставимы для равенства , когда значения сопоставимы для равенства. Функция, как prop_id_functor_law :: Cons a -> Bool, объявлена ​​для работы для всех значений Cons a, имеет или нет Eq a, поэтому проверка типа не позволит вам позвонить == по адресу Cons a в рамках реализации; он может не поддерживать равенство и гарантировать, что вы никогда не вызываете неподдерживаемые операции, является точкой проверки типа.Но если у вас вместо этого есть prop_id_functor_law :: Eq a => Cons a -> Bool, вы можете использовать == (и ответственность переместится на звонящих из prop_id_functor_law, чтобы они называли это для типов, поддерживающих равенство).