Go to the previous, next section.

Reduction of Lists

procedure+: reduce procedure initial list

Combines all the elements of list using the binary operation procedure. For example, using + one can add up all the elements:

(reduce + 0 list-of-numbers)

The argument initial is used only if list is empty; in this case initial is the result of the call to reduce. If list has a single argument, it is returned. Otherwise, the arguments are reduced in a left-associative fashion. For example:

(reduce + 0 '(1 2 3 4))                 =>  10
(reduce + 0 '(1 2))                     =>  3
(reduce + 0 '(1))                       =>  1
(reduce + 0 '())                        =>  0
(reduce + 0 '(foo))                     =>  foo
(reduce list '() '(1 2 3 4))            =>  (((1 2) 3) 4)

procedure+: reduce-right procedure initial list

Like reduce except that it is right-associative.

(reduce-right list '() '(1 2 3 4))      =>  (1 (2 (3 4)))

procedure+: fold-right procedure initial list

Combines all of the elements of list using the binary operation procedure. Unlike reduce and reduce-right, initial is always used:

(fold-right + 0 '(1 2 3 4))             =>  10
(fold-right + 0 '(foo))                 error--> Illegal datum
(fold-right list '() '(1 2 3 4))        =>  (1 (2 (3 (4 ()))))

Fold-right has interesting properties because it establishes a homomorphism between (cons, ()) and (procedure, initial). It can be thought of as replacing the pairs in the spine of the list with procedure and replacing the () at the end with initial. Many of the classical list-processing procedures can be expressed in terms of fold-right, at least for the simple versions that take a fixed number of arguments:

(define (copy-list list)
  (fold-right cons '() list))

(define (append list1 list2)
  (fold-right cons list2 list1))

(define (map p list) 
  (fold-right (lambda (x r) (cons (p x) r)) '() list))

(define (reverse items)
  (fold-right (lambda (x r) (append r (list x))) '() items))

procedure+: fold-left procedure initial list

Combines all the elements of list using the binary operation procedure. Elements are combined starting with initial and then the elements of list from left to right. Whereas fold-right is recursive in nature, capturing the essence of cdr-ing down a list and then computing a result, fold-left is iterative in nature, combining the elements as the list is traversed.

(fold-left list '() '(1 2 3 4))         =>  ((((() 1) 2) 3) 4)

(define (length list)
  (fold-left (lambda (sum element) (+ sum 1)) 0 list))

(define (reverse items)
  (fold-left (lambda (x y) (cons y x)) () items))

procedure+: there-exists? list predicate

Predicate must be a procedure of one argument. Applies predicate to each element of list, in order from left to right. If predicate is true for any element of list, the value yielded by predicate is immediately returned as the value of there-exists?; predicate will not be applied to the remaining elements of list. If predicate returns #f for all of the elements of list, then #f is returned.

procedure+: for-all? list predicate

Predicate must be a procedure of one argument. Applies predicate to each element of list, in order from left to right. If predicate returns #f for any element of list, #f is immediately returned as the value of for-all?; predicate will not be applied to the remaining elements of list. If predicate is true for all of the elements of list, then #t is returned.

Go to the previous, next section.