11

我想知道为什么 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(可能还有许多其他语言)中进行左折叠的设计?

4

4 回答 4

30

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

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

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

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

如果我们在一行上表示这个表达式,所有的括号都将关联到右边,因此名称为 right fold: (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与右折叠相比,参数以相反的顺序提供。

于 2012-09-05T20:29:06.287 回答
7

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

于 2012-09-05T20:33:54.597 回答
4

因为你写(a /: bs)foldLeft是简写;这是一个推a过所有 的运算符bs,因此很自然地以相同的方式编写函数(即(A,B) => A)。请注意,foldRight它是按其他顺序进行的。

于 2012-09-05T20:00:03.767 回答
2

假设你有这个:

List(4, 2, 1).foldLeft(8)(_ / _)

这与以下内容相同:

((8 / 4) / 2) / 1

看看第一个参数如何总是 te 累加器?按此顺序设置参数使占位符语法(下划线)直接转换为扩展表达式。

于 2012-09-06T04:16:07.960 回答