Next: , Previous: , Up: SRFI-1   [Contents][Index]

#### 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

The tail of the list; defaults to `'()`.

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.

Next: , Previous: , Up: SRFI-1   [Contents][Index]