Haskell: Foldl vs Foldr

fold_ideas.md

Foldl vs Foldr

I like to call foldr as "fold from the right", while foldl is "fold from the left".

This is due to the position of the seed value, and the order of evaluation in the AST. As you can see, for foldl the position of the seed value is on the left hand side of the tree, while foldr seed value is on the right hand side of the tree. In terms of total evaluation order (if we were to strictly evaluate the entirely cobined result), the foldr would evaluate from the right to left. While foldl would evaluate from left to right. The deepest node in the AST has to get evaluated first before the parent nodes can take the recursive value with the terminal value and apply both to its respective combining operation.

This order of evaluation can be illustrated with a simple left-associative minus combining operation:

foldr (-) 0 [1,2,3,4]

(1 - (2 - (3 - (4 - 0)))) = -2

  -
 / \
1   -
   / \
  2   -
     / \
    3   -
       / \
      4   0

foldl (-) 0 [1,2,3,4]

((((0 - 1) - 2) - 3) - 4) = -10

        -
       / \
      -   4
     / \
    -   3
   / \
  -   2
 / \
0   1

Another way to remember it is that foldr has a right biased tree, while foldl is a left biased tree. The tree is the AST. Looking at the tree again, one can also identify that the foldr preserves the order of the right-recursive list constructors. While the foldl reverses the order of list constructors.

It is interesting to note that most strict/imperative languages naturally gravitate to foldl, they obviously mostly call it "array reduce" or some variant of it. Strict languages don't have much use for foldr, and their reduce functions seem to always default to foldl. When programming imperatively and strictly, you tend to think left to right, hence evaluating/combining a list in a left to right manner induces the foldl bias.

Only foldr is lazy and can be used for codata/infinite streams. While foldl is tail-recursive (enhanced with strict application foldl' can avoid stack overflow). This is why foldr should be used by default in Haskellin order preserve laziness across function composition. However the laziness can only be taken advantage of, if the combining function is a data constructor, which can be lazily deconstructed.

Refer to https://wiki.haskell.org/Maintaining_laziness for more information!

This is due to the position of the seed value, and the order of evaluation in the AST.

What does "AST" stand for? What does it mean?

Abstract Syntax Tree