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

- 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. (unfold eof-object? values (lambda (x) (read)) (read)) ;; Copy a possibly non-proper list: (unfold not-pair? car cdr lis values) ;; Append HEAD onto TAIL: (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 eof-object? values (lambda (x) (read)) (read)) ;; (append-reverse rev-head tail) (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: srfi list spec filter, Previous: srfi list spec misc, Up: srfi list spec [Index]