7.5.3.5 Fold, Unfold & Map

Scheme Procedure: fold proc init lst1 lst2 …

Scheme Procedure: fold-right proc init lst1 lst2 …

Apply proc to the elements of lst1 lst2 … to build a result, and return that result.

Each proc call is (proc elem1 elem2 … previous), where elem1 is from lst1, elem2 is from lst2, and so on. previous is the return from the previous call to proc, or the given init for the first call. If any list is empty, just init is returned.

fold works through the list elements from first to last. The following shows a list reversal and the calls it makes,

(fold cons '() '(1 2 3))

(cons 1 '())
(cons 2 '(1))
(cons 3 '(2 1)
⇒ (3 2 1)

fold-right works through the list elements from last to first, ie. from the right. So for example the following finds the longest string, and the last among equal longest,

(fold-right (lambda (str prev)
              (if (> (string-length str) (string-length prev))
                  str
                  prev))
            ""
            '("x" "abc" "xyz" "jk"))
⇒ "xyz"

If lst1 lst2 … have different lengths, fold stops when the end of the shortest is reached; fold-right commences at the last element of the shortest. Ie. elements past the length of the shortest are ignored in the other lsts. At least one lst must be non-circular.

fold should be preferred over fold-right if the order of processing doesn’t matter, or can be arranged either way, since fold is a little more efficient.

The way fold builds a result from iterating is quite general, it can do more than other iterations like say map or filter. The following for example removes adjacent duplicate elements from a list,

(define (delete-adjacent-duplicates lst)
  (fold-right (lambda (elem ret)
                (if (equal? elem (first ret))
                    ret
                    (cons elem ret)))
              (list (last lst))
              lst))
(delete-adjacent-duplicates '(1 2 3 3 4 4 4 5))
⇒ (1 2 3 4 5)

Clearly the same sort of thing can be done with a for-each and a variable in which to build the result, but a self-contained proc can be re-used in multiple contexts, where a for-each would have to be written out each time.

Scheme Procedure: pair-fold proc init lst1 lst2 …

Scheme Procedure: pair-fold-right proc init lst1 lst2 …

The same as fold and fold-right, but apply proc to the pairs of the lists instead of the list elements.

Scheme Procedure: reduce proc default lst

Scheme Procedure: reduce-right proc default lst

reduce is a variant of fold, where the first call to proc is on two elements from lst, rather than one element and a given initial value.

If lst is empty, reduce returns default (this is the only use for default). If lst has just one element then that’s the return value. Otherwise proc is called on the elements of lst.

Each proc call is (proc elem previous), where elem is from lst (the second and subsequent elements of lst), and previous is the return from the previous call to proc. The first element of lst is the previous for the first call to proc.

For example, the following adds a list of numbers, the calls made to + are shown. (Of course + accepts multiple arguments and can add a list directly, with apply.)

(reduce + 0 '(5 6 7)) ⇒ 18

(+ 6 5)  ⇒ 11
(+ 7 11) ⇒ 18

reduce can be used instead of fold where the init value is an “identity”, meaning a value which under proc doesn’t change the result, in this case 0 is an identity since (+ 5 0) is just 5. reduce avoids that unnecessary call.

reduce-right is a similar variation on fold-right, working from the end (ie. the right) of lst. The last element of lst is the previous for the first call to proc, and the elem values go from the second last.

reduce should be preferred over reduce-right if the order of processing doesn’t matter, or can be arranged either way, since reduce is a little more efficient.

Scheme Procedure: unfold p f g seed [tail-gen]

unfold is defined as follows:

(unfold p f g seed) =
   (if (p seed) (tail-gen seed)
       (cons (f seed)
             (unfold p f g (g seed))))

p

Determines when to stop unfolding.

f

Maps each seed value to the corresponding list element.

g

Maps each seed value to next seed value.

seed

The state value for the unfold.

tail-gen

Creates the tail of the list; defaults to (lambda (x) '()).

g produces a series of seed values, which are mapped to list elements by f. These elements are put into a list in left-to-right order, and p tells when to stop unfolding.

Scheme Procedure: unfold-right p f g seed [tail]

Construct a list with the following loop.

(let lp ((seed seed) (lis tail))
   (if (p seed) lis
       (lp (g seed)
           (cons (f seed) lis))))

p

Determines when to stop unfolding.

f

Maps each seed value to the corresponding list element.

g

Maps each seed value to next seed value.

seed

The state value for the unfold.

tail-gen

Creates the tail of the list; defaults to (lambda (x) '()).

Scheme Procedure: map f lst1 lst2 …

Map the procedure over the list(s) lst1, lst2, … and return a list containing the results of the procedure applications. This procedure is extended with respect to R5RS, because the argument lists may have different lengths. The result list will have the same length as the shortest argument lists. The order in which f will be applied to the list element(s) is not specified.

Scheme Procedure: for-each f lst1 lst2 …

Apply the procedure f to each pair of corresponding elements of the list(s) lst1, lst2, …. The return value is not specified. This procedure is extended with respect to R5RS, because the argument lists may have different lengths. The shortest argument list determines the number of times f is called. f will be applied to the list elements in left-to-right order.

Scheme Procedure: append-map f lst1 lst2 …

Scheme Procedure: append-map! f lst1 lst2 …

Equivalent to

(apply append (map f clist1 clist2 ...))

and

(apply append! (map f clist1 clist2 ...))

Map f over the elements of the lists, just as in the map function. However, the results of the applications are appended together to make the final result. append-map uses append to append the results together; append-map! uses append!.

The dynamic order in which the various applications of f are made is not specified.

Scheme Procedure: map! f lst1 lst2 …

Linear-update variant of map – map! is allowed, but not required, to alter the cons cells of lst1 to construct the result list.

The dynamic order in which the various applications of f are made is not specified. In the n-ary case, lst2, lst3, … must have at least as many elements as lst1.

Scheme Procedure: pair-for-each f lst1 lst2 …

Like for-each, but applies the procedure f to the pairs from which the argument lists are constructed, instead of the list elements. The return value is not specified.

Scheme Procedure: filter-map f lst1 lst2 …

Like map, but only results from the applications of f which are true are saved in the result list.

This document was generated on April 20, 2013 using texi2html 5.0.