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

Question

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

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

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

Answer 1

您可能会问自己,该广义比较函数的类型是什么.首先,我们需要一种方法来编码组件类型:

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

我们真的无法用问题代替问号.结论是常规ADT是不够的,所以我们需要我们的第一语言扩展,GADTs:

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

为了保持与元组相同的严格行为,我认为你希望`Cons`在其第二个组件中是严格的(`Cons :: a - >!(Tuple as) - > Tuple(a':as)` ).给定`data T = T`,`(T,T)`中有五个值:`⊥`,`(⊥,⊥)`,`(T,⊥)`,`(⊥,T)`, `(T,T)`.但是,`Tuple'[(),()]`有额外的四个值`Cons_⊥`和`Cons _(Cons_⊥)`,其中`_`可以是`()`或`⊥`.此外,值得注意的是(对于可搜索性),`Tuple`也称为异类列表(或hlist). (3认同)

Answer 2

你总是可以用二进制元组重写任何n元组.例如,给定以下4元组:

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

您可以将其重写为:

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

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

需要注意的一点是,嵌套元组有更多可以位于底部的位置.一个unnested元组只能为整个值或特定元素设置底部.嵌套元组的任何"尾部"都可以有底部. (4认同)
这不是一个不明智的决定.n元组只是_different_而不是异类列表.我们有两者,我们可以同时使用两者,但是你没有理由在这个答案中给出的表述在任何地方都优于另一个. (3认同)
最初定义n元组是为了避免递归嵌套二进制元组所带来的无偿提升.不幸的是,这是一个不明智的决定,因为我们无法回头修复它.如果你以这种方式追溯定义n元组,你会破坏n-tuples的很多类型类实例,这些实例现在会与二进制元组的实例重叠. (2认同)

Answer 3

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

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