haskell - Haskell 和 SML/NJ 中的不同折叠

Question

在 foldl definition possible wrong in SML/NJ 110.75 ，我发现关系foldl (op -) 2 [1] = foldr (op -) 2 [1]持有。但是当我在 Haskell 中尝试上述时，我发现上面的关系在 Haskell 中重写为 foldl (-) 2 [1] == foldr (-) 2 [1]不成立。为什么是这样？ Haskell 对折叠的定义是否与 SML/NJ 不同？

谢谢

Answer 1

在 ML 中，两个折叠都具有相同的类型签名:

val foldl : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
val foldr : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

而在 Haskell 中，它们是不同的:

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

所以 Haskell 的 foldl 必然会对它给出的操作做一些不同的事情。

相似之处

两种语言在 foldr 计算的类型和值上都一致。 - 通过沿着列表向右移动折叠成一个值的列表，从右手端括起来:

foldr f init [x1, x2, ..., xn]    
 ==> f(x1, f(x2, ..., f(xn, init)...))

差异

首先，ML有

foldl f init [x1, x2, ..., xn]
 ==> f(xn,...,f(x2, f(x1, init))...)

所以ML的 foldl是左折叠，因为它将列表向左折叠而不是向右折叠。

而在 Haskell 中，你有

foldl f init [x1,x2,.....,xn]
 ==> f(f(...f(f(init,x1),x2),.....),xn)

在 Haskell 中， foldl是左折叠，因为它将初始值放在左侧并从左侧将列表括起来，但保留其顺序。

你的榜样

对于只有一个元素的列表，ML 做 f(x1,init)这给你 x1 - init这恰好与 foldr 相同的 xn - init因为第一个和最后一个元素是相同的。

相反，Haskell 做 f(init,x1)这给你 init - x1 .这就是为什么你会得到相反的答案。

稍长的例子

ML foldl :

foldl (op -) 100 [1,2,3,4]
 ==> 4 - (3 - (2 - (1 - 100)))
 ==> 102

ML/Haskell 的 foldr :

foldr (-) 100 [1,2,3,4]    or    foldr (op -) 100 [1,2,3,4]
 ==> 1 - (2 - (3 - (4 - 100)))
 ==> 98

Haskell 的 foldl :

foldl (-) 100 [1,]
 ==> (((100 - 1) - 2) - 3) - 4
 ==> 90

结论

是的， foldl 的两个定义不同. ML 的左边表示元素的顺序相反，而 Haskell 的左边表示括号的顺序相反。

只要你记住你使用的是哪个，这不是一个大问题。 (如果 init 和 x1 的类型不同，类型检查器会在你弄错时告诉你。)