23.8.6 Reducing

Function: reduce f ridentity ell

Syntax: reduce/stx f ridentity ell

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.

We typically use reduce when applying f is expensive and we would 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.

Examples:

;; take the max of a list of non-negative integers
(reduce max 0 '(1 2 3 4 5 6))
⇒ 6

(reduce + 0 '(0 1 2 3 4 5 6 7 8 9))
⇒ 45

Function: reduce* f ridentity ell

Syntax: reduce*/stx f ridentity ell

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

(reduce* f ridentity '()) ≡ ridentity
(reduce* f ridentity '(e1)) ≡ (f e1 ridentity)
                            ≡ e1
(reduce* f ridentity '(e1 e2 ...)) ≡
    (f e1 (reduce f ridentity (e2 ...)))

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

;; append a bunch of lists together
(reduce* append
         '()
         '((1 2 3)
           (4 5)
           (6 7 8 9)
           (0)))
⇒ (1 2 3 4 5 6 7 8 9 0)