Why does fold left expect (a -> b -> a) instead of (b -> a -> a)?

Question

I wonder why the function expected by fold left has type signature a -> b -> a instead of b -> a -> a. Is there a design decision behind this?

In Haskell, for example, I have to write foldl (\xs x -> x:xs) [] xs to reverse a list instead of the shorter foldl (:) [] xs (which would be possible with b -> a -> a). On the other hand, there are use cases which require the standard a -> b -> a. In Scala, this could be appending: xs.foldLeft(List.empty[Int]) ((xs, x) => xs:+x) which can be written as xs.foldLeft(List.empty[Int]) (_:+_).

Do proportionately more use cases occur requiring the given type signature instead of the alternative one, or are there other decisions which led to the design that fold left has in Haskell and Scala (and probably lots of other languages)?

Answer 1

Conceptually speaking, a right fold, say foldr f z [1..4] replaces a list of the following form

  :
 / \
1   :
   / \
  2   :
     / \
    3   :
       / \
      4  []

with the value of an expression of the following form

  f
 / \
1   f
   / \
  2   f
     / \
    3   f
       / \
      4   z

If we were to represent this expression on a single line, all parentheses would associate to the right, hence the name right fold: (1 `f` (2 `f` (3 `f` (4 `f` z)))). A left fold is dual in some sense to a right fold. In particular, we would like for the shape of the corresponding diagram for a left fold to be a mirror image of that for a left fold, as in the following:

        f
       / \
      f   4
     / \
    f   3
   / \
  f   2
 / \
z   1

If we were to write out this diagram on a single line, we would get an expression where all parentheses associate to the left, which jibes well with the name of a left fold:

((((z `f` 1) `f` 2) `f` 3) `f` 4)

But notice that in this mirror diagram, the recursive result of the fold is fed to f as the first argument, while each element of the list is fed as the second argument, ie the arguments are fed to f in reverse order compared to right folds.

Answer 2

The type signature is foldl :: (a -> b -> a) -> a -> [b] -> a; it's natural for the combining function to have the initial value on the left, because that's the way it combines with the elements of the list. Similarly, you'll notice foldr has it the other way round. The complication in your definition of reverse is because you're using a lambda expression where flip would have been nicer: foldl (flip (:)) [] xs, which also has the pleasant similarity between the concepts of flip and reverse.

Answer 3

Because you write (a /: bs) for foldLeft in short form; this is an operator which pushes a through all the bs, so it is natural to write the function the same way (i.e. (A,B) => A). Note that foldRight does it in the other order.