为什么Haskell不能为一维数组提供折叠？

Question

Data.Array不提供Array类型的折叠。 （第12章）

在真实世界哈斯克尔，原因据说是Array小号可能以不同的方式根据程序员的需要进行折叠：

首先，有几种折叠有意义。我们仍然可能想要折叠单个元素，但是现在我们也可以折叠行或列。除此之外，对于每次元素折叠，不再只有两个序列用于遍历。

这与List s不完全对应吗？代表例如具有多维List的矩阵，但仍存在为一维List s定义的折叠。

我失踪的微妙之处是什么？是否多维Array与Array的Array完全不同？

编辑：嗯，甚至多维数组确实有褶皱定义，在Data.Foldable实例的形式，[0]那么，如何适应，在与真实世界哈斯克尔报价？

[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 S'它们并不真正存在，因此。 Ix定义为实例的，同时也是实例类型的元组，如果你要考虑这样的元组作为索引类型为“多维” Array，去吧！但他们仍然只是元组。显然，Ix在这些元组上放置了一些线性顺序，但它是什么？你能在文档中找到任何告诉你的东西吗？

所以，我认为我们可以有把握地说，使用Ix定义的顺序折叠多维Array是不明智的，除非你真的不关心你会得到什么样的顺序中的元素。

对于Array的Array小号，另一方面，只有一个将它们组合，很像嵌套列表明智的方式：折叠每个内Array分别按照自己的元素的顺序，然后折根据外Array的元素的顺序的每个的结果。

---

现在，你很可能会反对说，因为有一维和多维Array s，而前者之间没有类型区分，可认为具有基于Ix实例明智倍订货，为什么不使用那默认排序？毕竟，已经有一个函数在列表中返回Array的元素。

事实证明，图书馆本身会同意你的看法，因为这正是Foldable实例的功能。

Answer 2

有折叠列出一个自然的方式，这是foldr。注意类型列表构造函数：

(:) :: a -> [a] -> [a] 
[] :: [a] 

与b更换的[a]的出现，我们可以得到以下类型：

f :: a -> b -> b 
z :: b 

而现在，当然，的foldr类型是基于这个原理：

foldr :: (a -> b -> b) -> b -> [a] -> b 

因此，考虑建设/列表的观察语义，foldr是一个的MOS自然。你可以阅读这个类型为“告诉我如何处理(:)以及如何处理[]，我将为你排除一个列表。”

Array没有此属性;你从一个关联列表（Ix i => [(i,a)]）建立一个数组，并且这个类型并没有真正公开任何递归结构：一个数组不是通过递归构造器从其他数组构建的，因为列表或树会是这样。