为什么fold会预期（a - > b - > a）而不是（b - > a - > a）？

Question

我想知道为什么预期左边的功能有类型签名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

因为您以简写形式编写(a /: bs)为foldLeft;这是一个运算符，它通过所有bs推动a，所以用同样的方式编写函数是很自然的（即(A,B) => A）。请注意，foldRight以其他顺序进行。

Answer 3

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

Answer 4

假设你有这样的：

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

这是一样的：

((8/4)/2)/1 

见的第一个参数是怎么总是忒蓄电池？按照此顺序具有参数可使占位符语法（下划线）直接转换为扩展表达式。