Haskell和SML/NJ中的不同折叠

Question

在foldl定义可能错误的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是左折叠,因为它将列表向左折叠而不是向右折叠.

而在哈斯克尔,你有

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

在haskell中,foldl左边是一个左侧折叠,它将初始值放在左边并从左侧括起列表,但保留其顺序.

你的榜样

对于只包含单个元素的列表,ML会f(x1,init)为您提供x1 - init与foldrs 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不同,类型检查器会告诉您何时出错.)

Answer 2

这有帮助吗？

mlFoldl :: (a -> b -> b) -> b -> [a] -> b
mlFoldl f = foldl (flip f)