= 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.
}}}