= 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, {{{#!haskell copy = foldr (:) [] }}} [wiki:/Functions/Map map] could be defined in terms of folding functions. {{{#!haskell map f = foldr ((:) . f) [] }}} 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. }}}