Next: , Previous: , Up: Lists   [Contents][Index]

### 7.8 Folding of Lists

SRFI 1 procedure: 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 procedure 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.

SRFI 1 procedure: 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.

obsolete procedure: fold-left proc knil list

Deprecated, use `fold` instead. Equivalent to

```(fold (lambda (acc elt) (proc elt acc)) knil list)
```
SRFI 1 procedure: 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 `fold`s uses a function with a right identity. The other four may not be performed with `reduce`).

```;; Take the max of a list of non-negative integers.
(reduce max 0 nums) ; i.e., (apply max 0 nums)
```
SRFI 1 procedure: reduce-right kons knil 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)
```
obsolete procedure: reduce-left f ridentity list

Deprecated, use `reduce` instead. Equivalent to

```(reduce (lambda (acc elt) (f elt acc)) ridentity list)
```

Next: , Previous: , Up: Lists   [Contents][Index]