Different fold in Haskell and SML/NJ

Question

In foldl definition possible wrong in SML/NJ 110.75, I found that the relation foldl (op -) 2 [1] = foldr (op -) 2 [1] holds. But when I tried the above in Haskell I found that the above relation rewritten in Haskell as foldl (-) 2 [1] == foldr (-) 2 [1] doesn't hold. Why is this? Does Haskell have different definition for fold than SML/NJ?

Thanks

Answer 1

In ML, both folds have the same type signature:

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

whereas in Haskell they're different:

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

so Haskell's foldl is necessarily doing something different with the operation it's been given.

Similarities

The two languages agree on both the type and the value computed by foldr - a list folded into a value by moving righwards along the list, bracketed from the right hand end:

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

Differences

First, ML has

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

So ML's foldl is a left fold in the sense that it folds the list leftwards instead of rightwards.

whereas in Haskell, you have

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

In haskell, foldl is a left fold in the sense that it puts the initial value at the left and brackets the list from the left, but retains its order.

Your example

With a list with just a single element, ML does f(x1,init) which gives you x1 - init which happens to be the same as foldr's xn - init because the first and last elements are the same.

Conversely, Haskell does f(init,x1) which gives you init - x1. That's why you get the opposite answer.

Slightly longer example

ML's foldl:

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

ML/Haskell's foldr:

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

Haskell's foldl:

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

Conclusion

Yes the two definitions are different for foldl. ML's left means opposite order of elements, whereas Haskell's left means opposite order of bracketing.

This isn't a big problem as long as you remember which one you're using. (If the types of init and x1 are different, the type checker will tell you when you get it wrong.)