Next: srfi ilists procs filter, Previous: srfi ilists procs misc, Up: srfi ilists procs [Index]
The fundamental ilist iterator.
First, consider the single ilist–parameter case. If:
ilist1 == (e1 e2 ... en)
then this procedure returns
(kons en ... (kons e2 (kons e1 knil)) ...)
That is, it obeys the (tail) recursion:
(ifold kons knil lis) ≡ (ifold kons (kons (icar lis) knil) (icdr lis)) (ifold kons knil '()) ≡ knil
Examples:
(ifold + 0 lis) ; Add up the elements of LIS.
(ifold ipair '() lis) ; Reverse LIS.
(ifold ipair tail rev-head) ; See APPEND-REVERSE.
;; How many symbols in LIS?
(ifold (lambda (x count)
(if (symbol? x) (+ count 1) count))
0
lis)
;; Length of the longest string in LIS:
(ifold (lambda (s max-len)
(max max-len (string-length s)))
0
lis)
If n ilist arguments are provided, then the kons function must take ‘n+1’ parameters: one element from each ilist, and the “seed” or fold state, which is initially knil. The fold operation terminates when the shortest ilist runs out of values:
(ifold ipair* '() (iq a b c) (iq 1 2 3 4 5)) ⇒ (c 3 b 2 a 1)
The fundamental ilist recursion operator.
First, consider the single ilist–parameter case. If:
ilist1 == (e1 e2 ... en)
then this procedure returns:
(kons e1 (kons e2 ... (kons en knil)))
That is, it obeys the recursion
(ifold-right kons knil lis) ≡ (kons (icar lis) (ifold-right kons knil (icdr lis))) (ifold-right kons knil '()) ≡ knil
Examples:
(ifold-right ipair '() lis) ; Copy LIS.
;; Filter the even numbers out of LIS.
(ifold-right (lambda (x l)
(if (even? x) (ipair x l) l))
'() lis)
If n ilist arguments are provided, then the kons procedure must take ‘n+1’ parameters: one element from each ilist, and the “seed” or fold state, which is initially knil. The fold operation terminates when the shortest ilist runs out of values:
(ifold-right ipair* '() (iq a b c) (iq 1 2 3 4 5)) ⇒ (a 1 b 2 c 3)
Analogous to fold, but kons is applied to successive sub–ilists of the ilists, rather than successive elements: that is, kons is applied to the ipairs making up the lists, giving this (tail) recursion:
(ipair-fold kons knil lis) ≡ (let ((tail (icdr lis))) (ipair-fold kons (kons lis knil) tail)) (ipair-fold kons knil '()) ≡ knil
Example:
(ipair-fold ipair '() (iq a b c)) ⇒ ((c) (b c) (a b c))
Hold the same relationship with ifold-right that
ipair-fold holds with ifold. Obeys the recursion:
(ipair-fold-right kons knil lis) ≡ (kons lis (ipair-fold-right kons knil (icdr lis))) (ipair-fold-right kons knil '()) ≡ knil
Example:
(ipair-fold-right ipair '() (iq a b c)) ⇒ ((a b c) (b c) (c))
ireduce is a variant of ifold.
ridentity should be a “right identity” of the procedure f: that is, for any value x acceptable to f:
(f x ridentity) ≡ x
ireduce has the following definition:
(ifold f (icar ilist) (icdr ilist))
in other words, we compute ‘(ifold f ridentity ilist)’.
Note that ridentity is used only in the empty–list case. You
typically use ireduce when applying f is expensive and
you’d like to avoid the extra application incurred when ifold
applies f to the head of ilist 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, ifold is
useful in many contexts where ireduce is not (consider the
examples given in the ifold definition: only one of the five
folds uses a function with a right identity. The other four may not be
performed with ireduce).
;; take the max of an ilist of non-negative integers (ireduce max 0 nums) ; i.e., (iapply max 0 nums)
ireduce-right is the fold–right variant of ireduce. It
obeys the following definition:
(ireduce-right f ridentity '()) ≡ ridentity (ireduce-right f ridentity (iq e1)) ≡ (f e1 ridentity) ≡ e1 (ireduce-right f ridentity (iq e1 e2 ...)) ≡ (f e1 (ireduce f ridentity (e2 ...)))
in other words, we compute ‘(ifold-right f ridentity ilist)’.
;; Append a bunch of ilists together. ;; I.e., (iapply iappend ilist-of-ilists) (ireduce-right iappend '() ilist-of-ilists)
iunfold is best described by its basic recursion:
(iunfold p f g seed) ≡
(if (p seed) (tail-gen seed)
(ipair (f seed)
(iunfold p f g (g seed))))
Determines when to stop unfolding.
Maps each seed value to the corresponding ilist element.
Maps each seed value to next seed value.
The “state” value for the unfold.
Creates the tail of the ilist; 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 ilist elements by f, producing the elements of the result ilist in a left–to–right order. p says when to stop.
iunfold is the fundamental recursive ilist constructor, just as
ifold-right is the fundamental recursive ilist consumer. While
iunfold may seem a bit abstract to novice functional programmers,
it can be used in a number of ways:
;; Ilist of squares: 1^2 ... 10^2
(iunfold (lambda (x) (> x 10))
(lambda (x) (* x x))
(lambda (x) (+ x 1))
1)
(iunfold null-ilist? icar icdr lis) ; Copy a proper ilist.
;; Read current input port into an ilist of values.
(iunfold eof-object? values (lambda (x) (read)) (read))
;; Copy a possibly non-proper ilist:
(iunfold not-ipair? icar icdr lis values)
;; Append HEAD onto TAIL:
(iunfold null-ilist? icar icdr head (lambda (x) tail))
Interested functional programmers may enjoy noting that
ifold-right and iunfold are in some sense inverses. That
is, given operations knull?, kar, kdr, kons, and
knil satisfying
(kons (kar x) (kdr x)) ⇒ x (knull? knil) ⇒ #t
then:
(ifold-right kons knil (iunfold knull? kar kdr x)) ⇒ x
and:
(iunfold knull? kar kdr (ifold-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”.
iunfold-right constructs an ilist with the following loop:
(let lp ((seed seed) (lis tail))
(if (p seed) lis
(lp (g seed)
(ipair (f seed) lis))))
Determines when to stop unfolding.
Maps each seed value to the corresponding ilist element.
Maps each seed value to next seed value.
The “state” value for the unfold.
Ilist 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 ilist elements by f, producing the elements of the result ilist in a right–to–left order. p says when to stop.
iunfold-right is the fundamental iterative ilist constructor,
just as ifold is the fundamental iterative ilist consumer. While
iunfold-right may seem a bit abstract to novice functional
programmers, it can be used in a number of ways:
;; Ilist of squares: 1^2 ... 10^2
(iunfold-right zero?
(lambda (x) (* x x))
(lambda (x) (- x 1))
10)
;; Reverse a proper ilist.
(iunfold-right null-ilist? icar icdr lis)
;; Read current input port into an ilist of values.
(iunfold-right eof-object? values (lambda (x) (read)) (read))
;; (iappend-reverse rev-head tail)
(iunfold-right null-ilist? icar icdr rev-head tail)
Interested functional programmers may enjoy noting that ifold and
iunfold-right are in some sense inverses. That is, given
operations knull?, kar, kdr, kons, and
knil satisfying:
(kons (kar x) (kdr x)) ⇒ x (knull? knil) ⇒ #t
then:
(ifold kons knil (iunfold-right knull? kar kdr x)) ⇒ x
and:
(iunfold-right knull? kar kdr (ifold kons knil x)) ⇒ x
This combinator presumably has some pretentious mathematical name; interested readers are invited to communicate it to the author.
proc is a procedure taking as many arguments as there are ilist
arguments and returning a single value. imap applies proc
element–wise to the elements of the ilists and returns an ilist of the
results, in order. The dynamic order in which proc is applied to
the elements of the ilists is unspecified.
(imap icadr (iq (a b) (d e) (g h)))
⇒ (b e h)
(imap (lambda (n) (expt n n)) (iq 1 2 3 4 5))
⇒ (1 4 27 256 3125)
(imap + (iq 1 2 3) (iq 4 5 6))
⇒ (5 7 9)
(let ((count 0))
(imap (lambda (ignored)
(set! count (+ count 1))
count)
(iq a b)))
⇒ (1 2) or (2 1)
The arguments to ifor-each are like the arguments to imap,
but ifor-each calls proc for its side effects rather than
for its values. Unlike imap, ifor-each is guaranteed to
call proc on the elements of the ilists in order from the first
element(s) to the last, and the value returned by ifor-each is
unspecified.
(let ((v (make-vector 5)))
(ifor-each (lambda (i)
(vector-set! v i (* i i)))
(iq 0 1 2 3 4))
v)
⇒ #(0 1 4 9 16)
Equivalent to:
(iapply iappend (imap f ilist1 ilist2 ...))
and.
(iapply iappend (imap f ilist1 ilist2 ...))
Map f over the elements of the ilists, just as in the imap
function. However, the results of the applications are appended
together (using iappend) to make the final result.
The dynamic order in which the various applications of f are made is not specified.
Example:
(iappend-map (lambda (x) (ilist x (- x))) (iq 1 3 8)) ⇒ (1 -1 3 -3 8 -8)
A variant of the imap procedure that guarantees to apply f
across the elements of the ilisti arguments in a left–to–right
order. This is useful for mapping procedures that both have side
effects and return useful values.
Like ifor-each, but f is applied to successive sub–ilists
of the argument ilists. That is, f is applied to the cells
of the ilists, rather than the ilists’ elements. These applications
occur in left–to–right order.
(ipair-for-each (lambda (ipair)
(display ipair)
(newline))
(iq a b c))
-| (a b c)
-| (b c)
-| (c)
Like imap, but only true values are saved.
(ifilter-map (lambda (x)
(and (number? x) (* x x)))
(iq a 1 b 3 c 7))
⇒ (1 9 49)
The dynamic order in which the various applications of f are made is not specified.
Next: srfi ilists procs filter, Previous: srfi ilists procs misc, Up: srfi ilists procs [Index]