7

我知道有长度为 2 到 15 的元组的Eq预定义实例。

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

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

4

4 回答 4

10

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

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 之前它们是不存在的。另外两个是需要比较的。当然有回报。我们得到了一个非常强大的元组类型，但是由于所有这些扩展，我们显然不能将这样的元组类型放入基础库中。

于 2013-02-04T15:27:30.137 回答
8

您始终可以根据二进制元组重写任何 n 元组。例如，给定以下 4 元组：

(1, 'A', "Hello", 20)

您可以将其重写为：

(1, ('A', ("Hello", (20, ()))))

将其视为一个列表，其中(,)扮演(:)（即“cons”）()的角色并扮演[]（即“nil”）的角色。使用这个技巧，只要你根据“二进制元组列表”来制定你的 n 元组，那么你可以无限期地扩展它，它会自动导出正确的Eq和Ord实例。

于 2013-02-04T11:55:10.830 回答
2

compareis的类型a -> a -> Ordering，这表明两个输入必须是相同的类型。根据定义，不同元组的元组是不同的类型。

但是，您可以通过使用HLists 或 GADTs来解决您的问题。

于 2013-02-04T11:12:42.353 回答
0

我只是想补充一下 ertes 的答案，即您不需要单个扩展来执行此操作。以下代码应符合 haskell98 和 2010 标准。除了单例元组之外，其中的数据类型可以一对一地映射到元组。如果你在二元组之后进行递归，你也可以实现这一点。

module Tuple (
    TupleClass,
    TupleCons(..),
    TupleNull(..)
    ) where

class (TupleClassInternal t) => TupleClass t

class TupleClassInternal t
instance TupleClassInternal ()
instance TupleClassInternal (TupleCons a b)

data (TupleClassInternal b) => TupleCons a b = TupleCons a !b deriving (Show)

instance (Eq a, Eq b, TupleClass b) => Eq (TupleCons a b) where
    (TupleCons a1 b1) == (TupleCons a2 b2) = a1 == a2 && b1 == b2

你也可以只推导出方程式。当然，使用 TypeOperators 看起来会更酷一些，但是 haskell 的列表系统也有语法糖。

于 2014-09-01T16:29:24.613 回答