index

I found a few ways to look at folds around the internet, and jotted them down here to have them in one place.

foldr :: (b -> a -> b) -> b -> [a] -> b
foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

foldl :: (a -> b -> b) -> b -> [a] -> b
foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

foldr f z [x1, x2, ..., xn] = x1 `f` (x2 `f` ... (xn `f` z)...)
foldl f z [x1, x2, ..., xn] = (...((z `f` x1) `f` x2) `f`...) `f` xn

http://foldr.com/ 1+(…)=∞

http://foldl.com/ (…)+1=∞

Mnemonic: the associativity corresponds with where the initial element is tossed.

R -> 1 2 3 4 ... n z
L -> z 1 2 3 4 ... n

And any hopes for laziness happen away in foldr in left argument, away from buried initial element. i.e., initial element is buried.

foldr :: (evolv -> nextElem -> evolv) -> evolv -> [nextElem] -> evolv
foldl :: (nextElem -> evolv -> evolv) -> evolv -> [nextElem] -> evolv

Mnemonic: associativity corresponds with whether initial element is far left or far right, which corresponds with function taking initial/evolving value first or second).

images

1. foldl f z

   

2. foldr f z

   

references:

• http://www.well-typed.com/blog/2014/04/fixing-foldl/
• https://en.wikipedia.org/wiki/Fold_(higher-order_function)