Different fold in Haskell and SML/NJ

Question 1

Long story short, they are essentially the same, with one minor difference: the order of the arguments passed to the operator (the combining function you pass to fold) are flipped. And since subtraction is not commutative, it will produce different results.

In Haskell (as well as OCaml, C++, Clojure, Common Lisp, Erlang, F#, JavaScript, PHP, Python, Ruby, Scala, and many others), for foldl, the supplied function's first argument is the initial value, or the "folded value so far", while the second argument is an element from the list.

However, in Standard ML, the supplied function's first argument is the element from the list, and the second argument is the initial value, or the "folded value so far".

Neither is "correct" or "incorrect". The order of arguments is purely a design decision. The way Haskell does it is more commonly used today across languages. And in a certain "graphical" way of looking at folding, it makes more sense. Why did SML define theirs the way they did? I am not sure. Perhaps so that the signatures of foldl and foldr will be the same.

Question 2

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.)

Question 3

Does this help?

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

Question 4

Expanding on Some Other Guy's answer:

From the Haskell Wiki:

-- if the list is empty, the result is the initial value z; else
-- apply f to the first element and the result of folding the rest
foldr f z []     = z 
foldr f z (x:xs) = f x (foldr f z xs) 

-- if the list is empty, the result is the initial value; else
-- we recurse immediately, making the new initial value the result
-- of combining the old initial value with the first element.
foldl f z []     = z                  
foldl f z (x:xs) = foldl f (f z x) xs

so foldl (-) 2 [1] is (2 - 1) and foldr (-) 2 [1] is (1 - 2)

From the SML Basis Library

foldl f init [x1, x2, ..., xn]
    returns

    f(xn,...,f(x2, f(x1, init))...)

    or init if the list is empty.

foldr f init [x1, x2, ..., xn]
    returns

    f(x1, f(x2, ..., f(xn, init)...))

    or init if the list is empty.

so foldl (op -) 2 [1] is fxn - init or 1 - 2, and foldr (op -) 2 [1] is fx1 - init. It is still 1 - 2, but only by coincidence. The answers diverge with a longer list, but not as much as the answers between Haskell and SML.