Next: , Previous: , Up: srfi list spec   [Index]

#### 2.2.5.6 Fold, unfold and map

Function: fold kons knil clist1 clist2 ...

The fundamental list iterator. First, consider the single list–parameter case: if `clist1 = (e1 e2 ... en)`, then this procedure returns:

```(kons en ... (kons e2 (kons e1 knil)) ... )
```

that is, it obeys the (tail) recursion:

```(fold kons knil lis) = (fold kons (kons (car lis) knil) (cdr lis))
(fold kons knil '()) = knil
```

Examples:

```(fold + 0 lis)			; Add up the elements of LIS.

(fold cons '() lis)		; Reverse LIS.

(fold cons tail rev-head)	; See APPEND-REVERSE.

;; How many symbols in LIS?
(fold (lambda (x count) (if (symbol? x) (+ count 1) count))
0
lis)

;; Length of the longest string in LIS:
(fold (lambda (s max-len) (max max-len (string-length s)))
0
lis)
```

If n list arguments are provided, then the kons function must take n+1 parameters: one element from each list, and the “seed” or fold state, which is initially knil. The fold operation terminates when the shortest list runs out of values:

```(fold cons* '() '(a b c) '(1 2 3 4 5)) => (c 3 b 2 a 1)
```

At least one of the list arguments must be finite.

Function: fold-right kons knil clist1 clist2 ...

The fundamental list recursion operator. First, consider the single list–parameter case. If `clist1 = (e1 e2 ... en)`, then this procedure returns:

```(kons e1 (kons e2 ... (kons en knil)))
```

that is, it obeys the recursion:

```(fold-right kons knil lis) = (kons (car lis) (fold-right kons knil (cdr lis)))
(fold-right kons knil '()) = knil
```

Examples:

```(fold-right cons '() lis)		; Copy LIS.

;; Filter the even numbers out of LIS.
(fold-right (lambda (x l) (if (even? x) (cons x l) l)) '() lis))
```

If n list arguments are provided, then the kons function must take n+1 parameters: one element from each list, and the “seed” or fold state, which is initially knil. The fold operation terminates when the shortest list runs out of values:

```(fold-right cons* '() '(a b c) '(1 2 3 4 5)) => (a 1 b 2 c 3)
```

At least one of the list arguments must be finite.

Function: pair-fold kons knil clist1 clist2 ...

Analogous to `fold`, but kons is applied to successive sublists of the lists, rather than successive elements; that is, kons is applied to the pairs making up the lists, giving this (tail) recursion:

```(pair-fold kons knil lis) = (let ((tail (cdr lis)))
(pair-fold kons (kons lis knil) tail))
(pair-fold kons knil '()) = knil
```

For finite lists, the kons function may reliably apply `set-cdr!` to the pairs it is given without altering the sequence of execution.

Example:

```;;; Destructively reverse a list.
(pair-fold (lambda (pair tail) (set-cdr! pair tail) pair) '() lis))
```

At least one of the list arguments must be finite.

Function: pair-fold-right kons knil clist1 clist2 ...

Holds the same relationship with `fold-right` that `pair-fold` holds with fold. Obeys the recursion:

```(pair-fold-right kons knil lis) =
(kons lis (pair-fold-right kons knil (cdr lis)))
(pair-fold-right kons knil '()) = knil
```

Example:

```(pair-fold-right cons '() '(a b c)) => ((a b c) (b c) (c))
```

At least one of the list arguments must be finite.

Function: reduce f ridentity list

`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.

You typically use `reduce` when applying f is expensive and you’d 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 (consider the examples given in the `fold` definition: only one of the five folds uses a function with a right identity; the other four may not be performed with `reduce`).

Note: MIT Scheme and Haskell flip f’s arguments order for their `reduce` and `fold` functions.

```;; Take the max of a list of non-negative integers.
(reduce max 0 nums) ; i.e., (apply max 0 nums)
```
Function: reduce-right f ridentity list

`reduce-right` is the `fold-right` variant of `reduce`. It obeys the following definition:

```(reduce-right f ridentity '()) = ridentity
(reduce-right f ridentity '(e1)) = (f e1 ridentity) = e1
(reduce-right f ridentity '(e1 e2 ...)) =
(f e1 (reduce f ridentity (e2 ...)))
```

in other words, we compute `(fold-right f ridentity list)`.

```;; Append a bunch of lists together.
;; I.e., (apply append list-of-lists)
(reduce-right append '() list-of-lists)
```
Function: unfold p f g seed [tail-gen]

`unfold` is best described by its basic recursion:

```(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) '())`.

In other words, we use g to generate a sequence of seed values:

```seed, g(seed), g2(seed), g3(seed), ...
```

These seed values are mapped to list elements by f, producing the elements of the result list in a left–to–right order. p says when to stop.

`unfold` is the fundamental recursive list constructor, just as `fold-right` is the fundamental recursive list consumer. While `unfold` may seem a bit abstract to novice functional programmers, it can be used in a number of ways:

```;; List of squares: 1^2 ... 10^2
(unfold (lambda (x) (> x 10))
(lambda (x) (* x x))
lambda (x) (+ x 1))
1)

(unfold null-list? car cdr lis) ; Copy a proper list.

;; Read current input port into a list of values.

;; Copy a possibly non-proper list:
(unfold not-pair? car cdr lis values)

(unfold null-list? car cdr head (lambda (x) tail))
```

Interested functional programmers may enjoy noting that `fold-right` and `unfold` are in some sense inverses. That is, given operations knull?, kar, kdr, kons, and knil satisfying:

```(kons (kar x) (kdr x)) = x and (knull? knil) = #t
```

then:

```(fold-right kons knil (unfold knull? kar kdr x)) = x
```

and:

```(unfold knull? kar kdr (fold-right kons knil x)) = x.
```

This combinator sometimes is called an “anamorphism”; when an explicit tail-gen procedure is supplied, it is called an “apomorphism”.

Function: unfold-right p f g seed [tail]

`unfold-right` constructs 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

List terminator; defaults to `'()`.

In other words, we use g to generate a sequence of seed values:

```seed, g(seed), g2(seed), g3(seed), ...
```

these seed values are mapped to list elements by f, producing the elements of the result list in a right–to–left order. p says when to stop.

`unfold-right` is the fundamental iterative list constructor, just as `fold` is the fundamental iterative list consumer. While `unfold-right` may seem a bit abstract to novice functional programmers, it can be used in a number of ways:

```;; List of squares: 1^2 ... 10^2
(unfold-right zero?
(lambda (x) (* x x))
(lambda (x) (- x 1))
10)

;; Reverse a proper list.
(unfold-right null-list? car cdr lis)

;; Read current input port into a list of values.

(unfold-right null-list? car cdr rev-head tail)
```

Interested functional programmers may enjoy noting that `fold` and `unfold-right` are in some sense inverses. That is, given operations knull?, kar, kdr, kons, and knil satisfying:

```(kons (kar x) (kdr x)) = x and (knull? knil) = #t
```

then:

```(fold kons knil (unfold-right knull? kar kdr x)) = x
```

and:

```(unfold-right knull? kar kdr (fold kons knil x)) = x.
```

This combinator presumably has some pretentious mathematical name; interested readers are invited to communicate it to the author.

Function: map proc clist1 clist2 ...

R5RS+ proc is a procedure taking as many arguments as there are list arguments and returning a single value. `map` applies proc element–wise to the elements of the lists and returns a list of the results, in order. The dynamic order in which proc is applied to the elements of the lists is unspecified.

```(map cadr '((a b) (d e) (g h))) =>  (b e h)

(map (lambda (n) (expt n n))
'(1 2 3 4 5))
=>  (1 4 27 256 3125)

(map + '(1 2 3) '(4 5 6)) =>  (5 7 9)

(let ([count 0])
(map (lambda (ignored)
(set! count (+ count 1))
count)
'(a b)))
=>  (1 2) or (2 1)
```

This procedure is extended from its R5RS specification to allow the arguments to be of unequal length; it terminates when the shortest list runs out.

At least one of the argument lists must be finite:

```(map + '(3 1 4 1) (circular-list 1 0)) => (4 1 5 1)
```
Function: for-each proc clist1 clist2 ...

R5RS+ The arguments to `for-each` are like the arguments to `map`, but `for-each` calls proc for its side effects rather than for its values. Unlike `map`, `for-each` is guaranteed to call proc on the elements of the lists in order from the first element(s) to the last, and the value returned by `for-each` is unspecified.

```(let ([v (make-vector 5)])
(for-each (lambda (i)
(vector-set! v i (* i i)))
'(0 1 2 3 4))
v)  =>  #(0 1 4 9 16)
```

This procedure is extended from its R5RS specification to allow the arguments to be of unequal length; it terminates when the shortest list runs out.

At least one of the argument lists must be finite.

Function: append-map f clist1 clist2 ...
Function: append-map! f clist1 clist2 ...

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.

Example:

```(append-map! (lambda (x) (list x (- x))) '(1 3 8))
=> (1 -1 3 -3 8 -8)
```

At least one of the list arguments must be finite.

Function: map! f list1 clist2 ...

Linear–update variant of `map`, `map!` is allowed, but not required, to alter the cons cells of list1 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, clist2, clist3, ... must have at least as many elements as list1.

Function: map-in-order f clist1 clist2 ...

A variant of the `map` procedure that guarantees to apply f across the elements of the listi arguments in a left–to–right order. This is useful for mapping procedures that both have side effects and return useful values.

At least one of the list arguments must be finite.

Function: pair-for-each f clist1 clist2 ...

Like `for-each`, but f is applied to successive sublists of the argument lists. That is, f is applied to the cons cells of the lists, rather than the lists’ elements. These applications occur in left–to–right order.

The f procedure may reliably apply `set-cdr!` to the pairs it is given without altering the sequence of execution.

```(pair-for-each (lambda (pair) (display pair) (newline)) '(a b c)) ==>
(a b c)
(b c)
(c)
```

At least one of the list arguments must be finite.

Function: filter-map f clist1 clist2 ...

Like `map`, but only true values are saved.

```(filter-map (lambda (x)
(and (number? x) (* x x)))
'(a 1 b 3 c 7))
=> (1 9 49)
```

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

At least one of the list arguments must be finite.

Next: , Previous: , Up: srfi list spec   [Index]