Mnemonics for Folds

Arialdo Martini — 17/06/2024 — functional programming haskell fsharp

I’ve always had trouble remembering the subtle differences between FoldLeft and FoldRight, and have constantly found myself consulting Hoogle over and over.
Overtime, I collected some mnemonics to help my gold fish memory.
I hope they can help you too.

FoldLeft
⇤ FoldRight
⇥

Accumulator

	FoldLeft ⇤	FoldRight ⇥
Accumulator	Left argument `(acc -> b -> acc) -> acc -> t b -> acc`	Right argument `(b -> acc -> acc) -> acc -> t b -> acc`
Initial value evaluation	Applied first at the left-hand side of the unrolled expression `foldl ● initial [a, b, c] (((initial ● a) ● b) ● c)`	Applied last at the right-hand side of an unrolled expression. `foldr ● initial [a, b, c] a ● (b ● (c ● initial))`
Associativity	Left `(((initial ● a) ● b) ● c)`	Right `(a ● (b ● ( c ● initial)))`
Function application (partial, on a list)	`foldl` is the outer function. `foldl f acc (x:xs) = foldl f (f acc x) xs`	`f` is the outer function. `foldr f acc (x:xs) = f x (foldr f acc xs)`

Left argument

(acc -> b -> acc) -> acc -> t b -> acc

Right argument

(b -> acc -> acc) -> acc -> t b -> acc

Initial value evaluation

Applied first at the left-hand side of the unrolled expression

foldl ● initial [a, b, c] (((initial ● a) ● b) ● c)

Applied last at the right-hand side of an unrolled expression.

foldr ● initial [a, b, c] a ● (b ● (c ● initial))

Associativity

Left

(((initial ● a) ● b) ● c)

Right

(a ● (b ● ( c ● initial)))

Function application
(partial, on a list)

foldl is the outer function.

foldl f acc (x:xs) = foldl f (f acc x) xs

f is the outer function.

foldr f acc (x:xs) = f x (foldr f acc xs)