higher-order-functions - 为什么 Haskell 不为一维数组提供折叠？

Question

Data.Array不为 Array 提供折叠类型。

在 Real World Haskell(第 12 章)中，据说原因是 Array s 可以根据程序员的需要以不同的方式折叠:

First of all, there are several kinds of folds that make sense. We might still want to fold over single elements, but we now have the possibility of folding over rows or columns, too. On top of this, for element-at-a-time folding, there are no longer just two sequences for traversal.

这不正是 List 的真实情况吗？ ?表示例如很常见一个多维矩阵 List ，但仍有为一维定义的折叠 List s。

我缺少的微妙之处是什么？是不是多维 Array与 Array 完全不同的 Array ?

编辑:嗯，即使是多维数组也确实定义了折叠，形式为 Data.Foldable .[0] 那么这与 Real World Haskell 的引用有什么关系呢？

[0] http://hackage.haskell.org/packages/archive/base/4.6.0.0/doc/html/Data-Foldable.html

Answer 1

既然你提到了“多维”之间的区别 Array和一个 Array的 Array s，这将很好地说明这一点，同时与列表进行比较。

折叠(在 Foldable 类意义上)是固有的线性操作，就像列表是固有的线性结构一样；右折叠通过将其构造函数与 foldr 的参数一对一匹配来完全表征列表。 .虽然你可以定义像 foldl 这样的函数同样，有一个标准的规范折叠的明确选择。
Array没有这样的透明结构可以在折叠中一对一匹配。它是一种抽象类型，可以访问由索引值提供的单个元素，索引值可以是具有 Ix 的任何类型。实例。因此，不仅没有单一的明显选择来实现折叠，而且也没有内在的线性结构。确实如此，Ix让您枚举一系列索引，但这更多的是实现细节。

多维怎么样Array ?它们实际上并不存在。 Ix为也是实例的类型的元组定义实例，如果您想将此类元组视为“多维”的索引类型 Array ， 前进!但它们仍然只是元组。显然，Ix在这些元组上放置一些线性顺序，但它是什么？你能在文档中找到任何告诉你的东西吗？

所以，我认为我们可以有把握地说折叠一个多维 Array使用 Ix 定义的顺序是不明智的，除非您真的不在乎获取元素的顺序。

对于 Array的 Array s，另一方面，只有一种合理的方式来组合它们，就像嵌套列表一样:折叠每个内部 Array分别按照自己的元素顺序，然后按照外层Array折叠每个的结果的元素顺序。

现在，您可能会合理地反对，因为一维和多维之间没有类型区别 Array s，并且可以假设前者具有基于 Ix 的合理折叠顺序。例如，为什么不默认使用该顺序？已经有一个函数可以返回 Array 的元素毕竟在一个列表中。

事实证明，图书馆本身会同意你的看法，因为这正是 Foldable 的内容。实例确实如此。