chickadee » srfi-1 » fold-right

The fundamental list recursion operator.

First, consider the single list-parameter case. If CLIST_1 = (E_1 E_2 ... E_N), then this procedure returns

(KONS E_1 (KONS E_2 ... (KONS E_N KNIL)))

That is, it obeys the recursion

(fold-right KONS KNIL LIS) = (KONS (car LIS) (fold-right KONS KNIL (cdr LIS)))
(fold-right KONS KNIL '()) = KNIL

Examples:

(fold-right cons '() lis)		; Copy LIS.
 
;; Filter the even numbers out of LIS.
(fold-right (lambda (x l) (if (even? x) (cons x l) l)) '() lis))

If N list arguments are provided, then the KONS function must take N+1 parameters: one element from each list, and the "seed" or fold state, which is initially KNIL. The fold operation terminates when the shortest list runs out of values:

(fold-right cons* '() '(a b c) '(1 2 3 4 5)) => (a 1 b 2 c 3)

At least one of the list arguments must be finite.