chickadee » srfi-1 » fold

The fundamental list iterator.

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

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

That is, it obeys the (tail) recursion

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

Examples:

(fold + 0 lis)			; Add up the elements of LIS.
 
(fold cons '() lis)		; Reverse LIS.
 
(fold cons tail rev-head)	; See APPEND-REVERSE.
 
;; How many symbols in LIS?
(fold (lambda (x count) (if (symbol? x) (+ count 1) count))
      0
      lis)
 
;; Length of the longest string in LIS:
(fold (lambda (s max-len) (max max-len (string-length s)))
      0
      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 cons* '() '(a b c) '(1 2 3 4 5)) => (c 3 b 2 a 1)

At least one of the list arguments must be finite.