haskell - 为什么我不能在 Haskell 中比较任意长度的元组？

Question

我知道有预定义的Eq实例 for tuples of lengths 2 to 15 .

为什么不将元组定义为某种递归数据类型以便它们可以被分解，从而允许为 compare 定义函数？适用于任意长度的元组？

毕竟，编译器确实支持任意长度的元组。

Answer 1

您可能会问自己，通用比较函数的类型是什么。首先，我们需要一种编码组件类型的方法:

data Tuple ??? = Nil | Cons a (Tuple ???)

真的没有什么是有效的，我们可以用它来代替问号。结论是常规的 ADT 是不够的，所以我们需要我们的第一个语言扩展 GADT:

data Tuple :: ??? -> * where
    Nil  :: Tuple ???
    Cons :: a -> Tuple ??? -> Tuple ???

然而，我们最终得到了问号。填补漏洞需要另外两个扩展，DataKinds 和 TypeOperators:

data Tuple :: [*] -> * where
    Nil  :: Tuple '[]
    Cons :: a -> Tuple as -> Tuple (a ': as)

如您所见，我们需要三个类型系统扩展来对类型进行编码。我们现在可以比较吗？嗯，这并不是那么容易回答，因为实际上如何编写独立的比较函数远非显而易见。幸运的是，类型类机制允许我们采用简单的递归方法。但是，这一次我们不仅在值级别上递归，还在类型级别上递归。显然空元组总是相等的:

instance Eq (Tuple '[]) where
    _ == _ = True

但是编译器再次提示。为什么？我们需要另一个扩展，FlexibleInstances，因为 '[]是具体类型。现在我们可以比较空元组，这并不是那么引人注目。那么非空元组呢？我们需要比较头部以及元组的其余部分:

instance (Eq a, Eq (Tuple as)) => Eq (Tuple (a ': as)) where
    Cons x xs == Cons y ys = x == y && xs == ys

似乎有道理，但是砰!我们收到另一个投诉。现在编译器需要 FlexibleContexts，因为我们在上下文中有一个不完全多态的类型， Tuple as .

总共有五个类型系统扩展，其中三个只是为了表达元组类型，在 GHC 7.4 之前它们是不存在的。另外两个是需要比较的。当然有返回。我们得到了一个非常强大的元组类型，但是由于所有这些扩展，我们显然不能将这样的元组类型放入基础库中。