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

Question

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

我试图对 Haskell 中的列表类型使用以下数据定义：

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

但是，-XDatatypeContexts 标志是必需的，默认情况下甚至从语言中删除。它被广泛认为是语言的错误特征。我也不想在我的 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 确实有效。此代码有效：

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 的值，如果没有扩展，您将无法做到这一点。但是，当 a 具有实现 Eq 的类型时，您可以告诉编译器如何比较两个 List a。有两种简单的方法可以做到这一点。最简单的是使用派生语句：

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

现在，只要您用实现 Eq 的内容填充 List 类型，该列表也可以使用 == 进行比较。无需限制 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：

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

Answer 2

通常的解决方法是使用这个结构：

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

注意到我已将 Eq a 作为约束添加到实例，而不是数据类型。这样，您可以比较您尝试编写的方式是否相等的所有列表都可以比较是否相等，但您也允许存在无法进行相等比较的事物列表。你会遇到的每个 Haskell 版本都支持这一点，即使是非常老的版本，也没有扩展。

当您想添加一个 Show 实例、一个 Ord 实例等时，这种方法也可以很好地扩展；要按照自己的方式进行操作，您必须不断返回并通过添加更多约束来使数据结构更具限制性（可能会破坏现有的代码，因为它不需要这些实例而可以正常工作）。然而，如果您让数据类型不受约束，只是让您的实例 Show a => Show (List a)、Ord a => Ord (List a) 等，那么您可以显示和顺序列表恰好支持的类型两者，但您仍然可以拥有（并显示）支持 Show 但不支持 Ord 的类型列表，反之亦然。

此外，还有很多有用的类型类用于参数化类型（例如 List a），要求它们在类型上是完全通用的范围。例如 Functor、Applicative、Monad；无法为您尝试创建的受限列表类型正确实现这些。

虽然可以像您尝试的那样创建受限列表（但只能通过使用扩展名，如您所见），但发现通常让你的数据类型在它们的类型参数中完全通用更有用，如果你的类型的特定用法需要对类型参数施加限制，你可以在 在该使用站点 上施加限制，而不是在 every 数据类型的使用。这应该是你的 "default setting";当你有充分的理由时离开它（你很可能在这里有这样的理由，但你没有在问题中给我们它，所以没有人可以推荐最好的处理方式）。

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

How to define Eq instance of List without GADTs or Datatype Contexts

haskell

list

compiler-flags

algebraic-data-types

gadt