{{ message }}

Instantly share code, notes, and snippets.

# CMCDragonkai/fold_ideas.md

Last active May 11, 2022

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

### varvir commented Feb 27, 2022 • edited

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?

### Peybro commented Mar 6, 2022

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