Next: srfi list spec filter, Previous: srfi list spec misc, Up: srfi list spec [Index]
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.
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.
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.
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.
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)
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)
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))))
Determines when to stop unfolding.
Maps each seed value to the corresponding list element.
Maps each seed value to next seed value.
The “state” value for the unfold.
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”.
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))))
Determines when to stop unfolding.
Maps each seed value to the corresponding list element.
Maps each seed value to next seed value.
The “state” value for the unfold.
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.
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)
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.
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.
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.
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.
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.
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]