[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

#### 7.5.3.5 Fold, Unfold & Map

- Scheme Procedure:
**fold***proc init lst1 … lstN* - Scheme Procedure:
**fold-right***proc init lst1 … lstN* Apply

`proc`to the elements of`lst1`…`lstN`to build a result, and return that result.Each

`proc`call is`(`

, where`proc``elem1`…`elemN``previous`)`elem1`is from`lst1`, through`elemN`from`lstN`.`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`through`lstN`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`lst`s. 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 … lstN* - Scheme Procedure:
**pair-fold-right***proc init lst1 … lstN* 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`(`

, where`proc``elem``previous`)`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.

[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

This document was generated on *February 3, 2012* using *texi2html 5.0*.