Version 10 (modified by schiptsov, 3 years ago) ( diff )



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)
                      (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
              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.
Note: See TracWiki for help on using the wiki.