list - 如何在没有 GADT 或数据类型上下文的情况下定义 List 的 Eq 实例

Question

我正在使用 Glasgow Haskell Compiler, Version 7.8.3, stage 2 booted by GHC version 7.6.3 .

我试图在 Haskell 中对 List 类型使用以下数据定义:

data Eq a => List a = Nil | Cons a (List a)

然而，-XDatatypeContexts默认情况下，flag 是必需的，已弃用，甚至从语言中删除。它被广泛认为是语言的一个错误特征。我也不想在我的 List 定义中使用特殊标志，因为我试图复制现有列表类型的功能。
然后我可以改用以下代码段:

data List a where
 Nil :: List a
 Cons :: Eq a => a -> List a -> List a

它运行良好。此解决方案的明显问题是现在我需要使用 -XGADTs标志，在这种情况下我仍然不想依赖它，因为列表的内置版本不需要运行。有没有办法限制 Cons 内的类型成为 Eq a这样我就可以在不需要编译器标志和不使用 derived 的情况下比较两个列表关键词？
剩下的代码如下:

instance Eq (List a) where
 (Cons a b) == (Cons c d) = (a == c) && (b == d)
 Nil == Nil = True
 _ == _ = False
testfunction = Nil :: List Int
main = print (if testfunction == Nil then "printed" else "not printed")

我看到以下解决方案有效:

data List a = Nil | Cons a (List a)
instance Eq a => Eq (List a) where
 (Cons a b) == (Cons c d) = (a == c) && (b == d)
 Nil == Nil = True
 _ == _ = False
testfunction = Nil :: List Int
main = print (if testfunction == Nil then "printed" else "not printed")

但是，由于某种原因，它不适用于 Eq 的手动定义(此处等于)。

class Equal a where  
 (=+=) :: a -> a -> Bool  
 (/+=) :: a -> a -> Bool  
 x =+= y = not (x /+= y)  
 x /+= y = not (x =+= y)
data List a = Nil | Cons a (List a)
instance Equal a => Equal (List a) where
 (Cons a b) =+= (Cons c d) = (a =+= c) && (b =+= d)
 Nil =+= Nil = True
 _ =+= _ = False
testfunction = Nil :: List Int
main = print (if testfunction =+= Nil then "printed" else "not printed")

我收到以下错误:

No instance for (Equal Int) arising from a use of ‘=+=’
    In the expression: testfunction =+= Nil
    In the first argument of ‘print’, namely
      ‘(if testfunction =+= Nil then "printed" else "not printed")’
    In the expression:
      print (if testfunction =+= Nil then "printed" else "not printed")

但是，通过使用 GADT，我可以证明我的 Equal 类确实可以运行。此代码有效:

class Equal a where  
 (=+=) :: a -> a -> Bool  
 (/+=) :: a -> a -> Bool  
 x =+= y = not (x /+= y)  
 x /+= y = not (x =+= y)
data List a where
 Nil :: List a
 Cons :: Equal a => a -> List a -> List a
instance Equal (List a) where
 (Cons a b) =+= (Cons c d) = (a =+= c) && (b =+= d)
 Nil =+= Nil = True
 _ =+= _ = False
testfunction = Nil :: List Int
main = print (if testfunction =+= Nil then "printed" else "not printed")

但是，我必须使用 instance Equal (List a) where而不是 instance Equal a => Equal (List a) where否则我会收到错误:

No instance for (Equal Int) arising from a use of ‘=+=’
    In the expression: testfunction =+= Nil
    In the first argument of ‘print’, namely
      ‘(if testfunction =+= Nil then "printed" else "not printed")’
    In the expression:
      print (if testfunction =+= Nil then "printed" else "not printed")

Answer 1

看起来您正试图将列表限制为只能包含实现 Eq 的值。 ，如果没有扩展，你就无法做到这一点。但是，您可以告诉编译器如何比较两个 List a s 当 a有一个实现 Eq 的类型.有两种简单的方法可以做到这一点。最简单的是使用派生语句:

data List a = Nil | Cons a (List a) deriving (Eq)

或者您可以手动定义它:

instance Eq a => Eq (List a) where
    (Cons a b) == (Const c d) = (a == c) && (b == d)
    Nil == Nil = True
    _ == _ = False

现在每当您填写您的 List输入实现 Eq 的东西，该列表也将使用 == 进行比较.没有必要限制可以在 Cons 内的值。 .你当然可以有一个正常的函数列表，比如

fs1 :: [Int -> Int]
fs1 = [(+1), (*3), (+2), (*4)]

或者在你的情况下

fs2 :: List (Int -> Int)
fs2 = Cons (+1) $ Cons (*3) $ Cons (+2) $ Cons (*4) Nil

哪个可以用作

> map ($ 10) fs1
[11, 30, 12, 40]

并给予

map' :: (a -> b) -> List a -> List b
map' f Nil = Nil
map' f (Cons x xs) = Cons (f x) (map' f xs)

然后

> map' ($ 10) fs2
Cons 11 (Cons 30 (Cons 12 (Cons 40 Nil)))

尽管要在 GHCi 中实际查看它，您还应该派生 Show :

data List a = Nil | Cons a (List a) deriving (Eq, Show)

还有一些其他有用的类型类也可以在 GHC 中派生出来。

使其适用于您的自定义 Equal类型类，您必须手动编写多个实例:

class Equal a where
    (=+=) :: a -> a -> Bool
    (/+=) :: a -> a -> Bool
    x =+= y = not (x /+= y)
    x /+= y = not (x =+= y)

instance Equal Int where
    x =+= y = x == y

instance Equal a => Equal (List a) where
    (Cons a b) =+= (Cons c d) = (a =+= c) && (b =+= d)
    Nil =+= Nil = True
    _ =+= _ = False

现在因为你有一个实例 Equal Int和 Equal a => Equal (List a) ，您可以比较两个 List Int s:

> let x = Cons 1 (Cons 2 (Cons 3 Nil)) :: List Int
> let y = Cons 1 (Cons 2 (Cons 3 Nil)) :: List Int
> x =+= y
True
> x =+= Nil
False

对于您想存储在 List 中的任何类型并使用 =+=在，你必须实现 Equal对于那种类型。