为什么折叠离开期望(a - > b - > a)而不是(b - > a - > a)？

Question

我想知道为什么fold左边的函数有类型签名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与右折叠相比,参数以相反的顺序被馈送.

Answer 2

类型签名是foldl :: (a -> b -> a) -> a -> [b] -> a; 组合函数在左侧具有初始值是很自然的,因为这是它与列表元素结合的方式.同样地,你会注意到foldr它反过来了.你在反向定义中的复杂性是因为你正在使用一个flip更好的lambda表达式foldl (flip (:)) [] xs,它在翻转和反向概念之间也具有令人愉快的相似性.