37

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

使这些类型等效将使在元组上编写函数变得更加容易。例如，您可以只定义一个适用于所有元组的 zip 函数，而不是定义 zip、zip2、zip3 等。

当然，您可以使用嵌套的 2 元组，但它很难看，并且没有执行嵌套的规范方法（即我们应该嵌套在左侧还是右侧？）。

4

2 回答 2

35

该类型(a,b,c,d)具有与 不同的性能配置文件(a,(b,(c,(d,()))))。通常，索引到 n 元组需要O(1)，而索引到 n 个嵌套元组的“hlist”需要O(n)。

也就是说，您应该查看 Oleg 关于HLists的经典作品。使用 HLists 需要大量使用类型级编程，而且有些粗略。许多人认为这是不可接受的，并且在早期的 Haskell 中是不可用的。今天表示 HList 的最佳方式可能是使用 GADT 和 DataKinds

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

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

我考虑过编写一个类似 HList 的库，该库使用数组并unsafeCoerce在底层获得类似元组的性能，同时坚持通用接口。我没做过，但应该不会太难。

编辑：我想得越多，当我有时间的时候，我就越倾向于一起破解一些东西。Andreas Rossberg 提到的重复复制问题可能可以使用流融合或类似技术来消除。

于 2013-02-20T07:15:14.343 回答
23

Haskell 中的主要问题是嵌套元组由于懒惰而允许附加值。例如，类型(a,(b,())由 all (x,_|_)or占据(x,(y,_|_))，而扁平元组则不是这种情况。这些值的存在不仅在语义上不方便，还会使元组更难优化。

不过，用严格的语言来说，您的建议确实是一种可能性。但它仍然引入了一个性能缺陷：实现仍然希望扁平化元组。因此，在您实际以归纳方式构造或解构它们的情况下，它们将不得不进行大量重复复制。当您使用非常大的元组时，这可能是个问题。

于 2013-02-20T07:34:16.023 回答