Fold (higher-order Function) - Universality

Universality

Fold is a polymorphic function. For any g having a definition

g = v g (x:xs) = f x (g xs)

then g can be expressed as

g = foldr f v

We can also implement a fixed point combinator using fold, proving that iterations can be reduced to folds:

fix f = foldr (\_ -> f) undefined (repeat undefined)