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

Question

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

在 Real World Haskell（第 12 章）中，据说原因是Arrays 可以根据程序员的需要以不同的方式折叠：

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

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

我缺少什么微妙之处？是多维与s 的Array一个足够不同吗？ArrayArray

编辑：嗯，即使是多维数组也确实以 .[0] 实例的形式定义了折叠，Data.Foldable那么这如何与 Real World Haskell 引用相匹配？

score 8 · Accepted Answer

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

折叠（在Foldable类意义上）本质上是线性操作，就像列表本质上是线性结构一样；右折叠通过将其构造函数与的参数一对一匹配来完全表征列表foldr。虽然您也可以定义类似foldl的函数，但可以明确选择标准的规范折叠。

Array没有这样的透明结构，可以在折叠中一对一匹配。它是一种抽象类型，可以访问由索引值提供的各个元素，索引值可以是任何具有Ix实例的类型。因此，实现折叠不仅没有单一的明显选择，也没有内在的线性结构。它确实发生了Ix让您枚举一系列索引的情况，但这更像是一个实现细节而不是其他任何东西。

那么多维Arrays呢？它们实际上并不存在。Ix为同样是实例的类型的元组定义实例，如果您想将此类元组视为“多维”的索引类型Array，请继续！但它们仍然只是元组。显然，Ix在这些元组上设置了一些线性顺序，但它是什么？你能在文档中找到任何告诉你的东西吗？

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

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

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

事实证明，库本身会同意你的观点，因为这正是Foldable实例所做的。

score 4 · Accepted Answer

折叠列表有一种自然的方式，即foldr. 注意列表构造函数的类型：

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

替换出现的[a]with b，我们得到以下类型：

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

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

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

因此，鉴于列表的构造/观察语义，foldr这是最自然的一种。您可以将类型理解为“告诉我如何处理 a(:)以及如何处理 a []，我会为您处理掉一个列表”。

Array没有这个属性；你从关联列表Ix i => [(i,a)]（

2 回答 2