7.8 Folding of Lists

SRFI 1 procedure: fold kons knil clist₁ clist₂ …

The fundamental list iterator.

First, consider the single list-parameter case. If clist₁ = (e1 e2 … en), then this procedure returns

(kons en … (kons e2 (kons e1 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 procedure 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.

SRFI 1 procedure: fold-right kons knil clist₁ clist₂ …

The fundamental list recursion operator.

First, consider the single list-parameter case. If clist₁ = (e1 e2 … en), then this procedure returns

(kons e1 (kons e2 … (kons en 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.

obsolete procedure: fold-left proc knil list

Deprecated, use fold instead. Equivalent to

(fold (lambda (acc elt) (proc elt acc)) knil list)

SRFI 1 procedure: reduce f ridentity list

reduce is a variant of fold.

ridentity should be a "right identity" of the procedure f—that is, for any value x acceptable to f,

(f x ridentity) = x

reduce has the following definition:

If list = (), return ridentity;
Otherwise, return (fold f (car list) (cdr list)).

...in other words, we compute (fold f ridentity list).

Note that ridentity is used only in the empty-list case. You typically use reduce when applying f is expensive and you’d like to avoid the extra application incurred when fold applies f to the head of list and the identity value, redundantly producing the same value passed in to f. For example, if f involves searching a file directory or performing a database query, this can be significant. In general, however, fold is useful in many contexts where reduce is not (consider the examples given in the fold definition—only one of the five folds uses a function with a right identity. The other four may not be performed with reduce).

;; Take the max of a list of non-negative integers.
(reduce max 0 nums) ; i.e., (apply max 0 nums)

SRFI 1 procedure: reduce-right kons knil list

reduce-right is the fold-right variant of reduce. It obeys the following definition:

(reduce-right f ridentity '()) = ridentity
(reduce-right f ridentity '(e1)) = (f e1 ridentity) = e1
(reduce-right f ridentity '(e1 e2 …)) =
    (f e1 (reduce f ridentity '(e2 …)))

...in other words, we compute (fold-right f ridentity list).

;; Append a bunch of lists together.
;; I.e., (apply append list-of-lists)
(reduce-right append '() list-of-lists)

obsolete procedure: reduce-left f ridentity list

Deprecated, use reduce instead. Equivalent to

(reduce (lambda (acc elt) (f elt acc)) ridentity list)