# foldr

`foldr`

and `foldl`

are *enzymes* which generalize traversing and rebuilding of a list structure by taking a *combinator* and an *initial value* as parameters.

Abstractly, `foldr`

is a function that replaces all occurrences of `Cons`

in a list by `f`

applied to `x`

and `xs`

, and all occurrences of `Nil`

by `z`

. So,

copy = foldr (:) []

map could be defined in terms of folding functions.

map f = foldr ((:) . f) []

see also Folds

(define foldr (lambda (f z xs) (if (null? xs) z (f (car xs) (foldr f z (cdr xs))))))

in terms of constant-space foldl at the cost of extra reverse

(define (foldr f z xs) (foldl (flip f) z (reverse xs))))

foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs)

foldr k z = go where go [] = z go (y:ys) = y `k` go ys

foldr(F, Z, [H|T]) -> F(H, foldr(F, Z, T)); foldr(F, Z, []) when is_function(F, 2) -> Z.

Last modified
3 years ago
Last modified on Nov 15, 2018, 6:25:05 AM

**Note:**See TracWiki for help on using the wiki.