= 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. [wiki:/Functions/Map map] could be defined in terms of folding functions. see also [wiki:Folds] {{{#!scheme (define foldr (lambda (f z xs) (if (null? xs) z (f (car xs) (foldr f z (cdr xs)))))) }}} in terms of constant-space [wiki:Functions/Foldl foldl] at the cost of extra [wiki:Functions/Reverse reverse] {{{#!scheme (define (foldr f z xs) (foldl (flip f) z (reverse xs)))) }}} {{{#!haskell foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs) }}} {{{#!haskell foldr k z = go where go [] = z go (y:ys) = y `k` go ys }}} {{{#!prolog foldr(F, Z, [H|T]) -> F(H, foldr(F, Z, T)); foldr(F, Z, []) when is_function(F, 2) -> Z. }}}