scala - 为什么向左折叠期望(a -> b -> a)而不是(b -> a -> a)？

Question

我想知道为什么 fold left 期望的函数有类型签名 a -> b -> a而不是 b -> a -> a .这背后是否有设计决策？

例如，在 Haskell 中，我必须写 foldl (\xs x -> x:xs) [] xs反转列表而不是较短的 foldl (:) [] xs (这将是可能的 b -> a -> a )。另一方面，有些用例需要标准 a -> b -> a .在 Scala 中，可以附加:xs.foldLeft(List.empty[Int]) ((xs, x) => xs:+x)可以写成xs.foldLeft(List.empty[Int]) (_:+_) .

是否相应地出现更多的用例需要给定类型签名而不是替代类型签名，或者是否有其他决定导致在 Haskell 和 Scala(可能还有许多其他语言)中进行左折叠的设计？

Answer 1

从概念上讲，右折叠，比如 foldr f z [1..4]替换以下形式的列表

  :
 / \
1   :
   / \
  2   :
     / \
    3   :
       / \
      4  []

具有以下形式的表达式的值

  f
 / \
1   f
   / \
  2   f
     / \
    3   f
       / \
      4   z

如果我们在一行上表示这个表达式，所有的括号都将关联到右边，因此名称右折叠: (1 `f` (2 `f` (3 `f` (4 `f` z)))) .左折叠在某种意义上与右折叠是双重的。特别是，我们希望左折叠的相应图表的形状是左折叠的镜像，如下所示:

        f
       / \
      f   4
     / \
    f   3
   / \
  f   2
 / \
z   1

如果我们要在一行上写出这个图，我们会得到一个表达式，其中所有括号都与左侧相关联，这与左折叠的名称非常吻合:

((((z `f` 1) `f` 2) `f` 3) `f` 4)

但请注意，在这个镜像图中，折叠的递归结果被馈送到 f。作为第一个参数，而列表的每个元素作为第二个参数提供，即参数提供给 f。与右折叠相比，顺序相反。