为什么 (a,b,c,d) 不是 (a,(b,(c,(d,())))) 中的糖？

Question

很明显，任何 n 元组都可以用一堆嵌套的二元组来表示。那么在 Haskell 中它们为什么不是同一件事呢？这样会破坏什么吗？

使这些类型等价将使得在元组上编写函数变得更加容易。例如，你可以只定义一个 zip 函数，而不是定义 zip、zip2、zip3 等等多个函数来处理不同的元组。

当然，你可以使用嵌套的二元组，但这样做很丑陋，并且没有一种标准的嵌套方式（即应该向左还是向右嵌套？）。

- Mike Izbicki

---

https://dev59.com/om3Xa4cB1Zd3GeqPj-QP - John Rivers

Answer 1

类型(a,b,c,d)与(a,(b,(c,(d,()))))的性能特征不同。一般情况下，对n元组的索引需要O(1)，而对n个嵌套元组的“hlist”进行索引需要O(n)。

话虽如此，您应该查看Oleg关于HLists的经典作品。使用HLists需要广泛且有些棘手的类型级编程。许多人认为这是不可接受的，并且在早期的Haskell中不可用。今天表示HList最好的方法可能是使用GADTs和DataKinds。

data HList ls where
  Nil  :: HList '[]
  Cons :: x -> HList xs -> HList (x ': xs)

这样做可以实现规范的嵌套，并使您编写的函数适用于此类型的所有实例。您可以使用与printf中使用的技术相同的技术来实现多路zipWith。生成此类型的适当镜头是一个更有趣的难题（提示：使用类型级自然数和类型族进行索引）。

我考虑过编写类似于HList的库，该库在底层使用数组和unsafeCoerce以获得类似元组的性能，同时保持通用界面。我还没有完成它，但它不应该过于困难。

编辑：我越想越倾向于在有时间时拼凑出一些东西。使用流融合或类似技术可能可以消除Andreas Rossberg提到的重复复制问题。

- Philip JF

---

我看过Oleg的工作，这启发了我开始构思这个基本想法。然而，他的库语法（以及我所见到的所有变体）在实践中使用起来非常糟糕。此外，我没有意识到嵌套元组会带来O(n)的性能损失。难道展开操作不能由编译器完成以生成O(1)的结果吗？ - Mike Izbicki

我认为你所说的是运行时性能，而不是编译时性能。对于嵌套元组来说，编译时性能不如其他类型也是可以理解的，但这似乎并不是什么大问题。 - Mike Izbicki

@MikeIzbicki，你认为基于dataKinds的类型是不可接受的吗？a：b：c：[]？如果这是你关心的问题，我们可以为值级别设计更好的构造函数。 - Philip JF

@PhilipJF 我决定使用向量作为基础来创建元组类型，就像你所说的那样。我解决了每次进行元组-cons 时复制向量的问题，通过使向量额外大并使用可变向量。至少目前我认为它是有效的。现在它还很简陋，所以我会尽力在这个星期把它整理得更合理，并将其放在 Github 上。 - Mike Izbicki

如果有人在未来阅读此内容，这是 Github 项目的链接：https://github.com/mikeizbicki/vector-heterogenous#hvector - Mike Izbicki

Answer 2

在 Haskell 中，嵌套元组的主要问题是由于惰性求值，它允许添加额外的值。例如，类型 (a,(b,()) 包含所有形如 (x,_|_) 或 (x,(y,_|_)) 的值，但平面元组却不是这样。这些值的存在不仅在语义上不方便，而且也会使元组更加难以优化。

然而，在严格语言中，您的建议确实是一个可能性。但它仍然引入了性能陷阱：实现仍然需要展开元组。因此，在您实际上通过归纳构造或解构它们的情况下，它们将不得不进行大量重复的复制。当您使用非常大的元组时，这可能是一个问题。

- Andreas Rossberg

---

如果我们使严格嵌套的元组与它们的扁平化对应物同构，例如：(a,!(b,!(c,!()))) ~ (a,b,c)，会怎么样？此外，所有这些复制操作不是可以在编译时而不是运行时完成吗？ - Mike Izbicki

@MikeIzbicki，据我所知，在Haskell中没有类型“（a，！（...））”。您只能将数据类型构造函数的参数注释为严格。关于复制，当您通过递归其长度来构造或解构元组时，当然不需要在其中写下元组文字，但是我看不到避免它的方法。 - Andreas Rossberg

我想知道是否有一种方法可以保持元组当前的表示方式，但提供类似于嵌套元组的接口。基本上，让元组以同样的方式工作，但也使得编写通用代码更容易，例如递归类型类实例。 - Tikhon Jelvis

如果表示包括一个指向数组的指针来托管元组的元素，以及一个已知大小的元组数字（<= 实际数组大小可能要大得多，或者通过指数调整大小增长），则复制只需复制这两个字段。实际数组可以共享，我想。 - Will Ness

@WillNess，当然，但是在任何地方都需要额外的间接和额外的分配成本远比它可以解决的问题更糟糕。 - Andreas Rossberg