This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi116@nospamsrfi.schemers.org
. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.
Scheme currently does not provide immutable pairs corresponding to its existing mutable pairs, although most uses of pairs do not exploit their mutability. The Racket system takes the radical approach of making Scheme's pairs immutable, and providing a minimal library of mutable pairs with procedures named mpair?, mcons, mcar, mcdr, setmcar!, setmcdr!
. This SRFI takes the opposite approach of leaving Scheme's pairs unchanged and providing a full set of routines for creating and dealing with immutable pairs. The sample implementation is portable (to systems with SRFI 9) and efficient.
The first question about this library is why it should exist at all. Why not simply eliminate mutability from Scheme's ordinary pairs and use a version of SRFI1 that treats the linearupdate procedures (with !
) as identical to their functional counterparts, as Racket does? The main answer is that this approach breaks R^{5}RS and R^{7}RSsmall. All the data structures in these versions of Scheme are inherently mutable, and portable code is allowed to depend on that property.
R^{6}RS segregates setcar!
and setcdr!
into a separate library, thus allowing implementations to provide immutable Scheme pairs if this library is not (transitively) imported into a program, and mutable ones if it is. However, it is not possible to write portable R^{6}RS programs that differentiate between mutable and immutable pairs, for example by using immutable pairs most of the time and mutable pairs where necessary.
Because of the Liskov Substitution Principle, it is not possible to treat immutable pairs as either a subtype or a supertype of mutable ones; they must be distinct, and if operations are to apply to both, they can do so only by ad hoc polymorphism of the kind that Scheme traditionally avoids for several reasons, including clarity, efficiency, and flexibility. This proposal, therefore, treats mutable and immutable pairs separately, while allowing easy conversion from one to the other.
Rather than attempting to design this library from scratch, I have chosen the conservative option of modifying SRFI 1. Consequently, most of the rationale given in that document applies to this one as well. I have made the following changes:
!
i
at a judicious place in each identifier, usually at the beginning. However, because "icons" means something else in both ordinary English and computer jargon, the basic constructor and its immediate relatives are named ipair
, xipair
and ipair*
instead.apply
for applying a procedure to an immutable list of arguments.Note: In the prose, immutable pairs and lists are known as ipairs and ilists throughout.
Here is a short list of the procedures provided by this SRFI.
ipair ilist xipair ipair* makeilist ilisttabulate ilistcopy iiota
ipair? properilist?/ilist? dottedilist? notipair? nullilist? ilist=
icar icdr ... icddadr icddddr ilistref ifirst isecond ithird ifourth ififth isixth iseventh ieighth ininth itenth icar+icdr itake idrop/ilisttail itakeright idropright isplitat ilast lastipair
ilength iappend iconcatenate ireverse iappendreverse izip iunzip1 iunzip2 iunzip3 iunzip4 iunzip5 icount
imap iforeach ifold iunfold ipairfold ireduce ifoldright iunfoldright ipairfoldright ireduceright iappendmap ipairforeach ifiltermap imapinorder
ifilter ipartition iremove
imember imemq imemv ifind ifindtail iany ievery ilistindex itakewhile idropwhile ispan ibreak
idelete ideleteduplicates
iassoc iassq iassv ialistcons ialistdelete
replaceicar replaceicdr
pair>ipair ipair>pair list>ilist ilist>list tree>itree itree>tree gtree>itree gtree>tree
iapply
ipaircomparator ilistcomparator makeilistcomparator makeimproperilistcomparator makeicarcomparator makeicdrcomparator
A set of general criteria guided the design of the SRFI1 library that underlies this library. They are reproduced here.
Listfiltering procedures such as ifilter
or idelete
do not disorder
lists. Elements appear in the answer list in the same order as they appear in
the argument list. This constrains implementation, but seems like a desirable
feature, since in many uses of lists, order matters. (In particular,
disordering an association list is definitely a bad idea.)
Contrariwise, although the sample implementations of the listfiltering procedures share longest common tails between argument and answer lists, it is not part of the spec.
Because ilists are an inherently sequential data structure (unlike, say,
vectors), inspection procedures such as ifind
, ifindtail
, iforeach
, iany
and ievery
commit to a lefttoright traversal order of their argument list.
However, constructors, such as
and the mapping
procedures (ilisttabulate
iappendmap
, ipairforeach
, ifiltermap
,
imapinorder
), do not specify the dynamic order in which their procedural
argument is applied to its various values.
Predicates return useful true values wherever possible. Thus iany
must return
the true value produced by its predicate, and ievery
returns the final true
value produced by applying its predicate argument to the last element of its
argument list.
No special status is accorded Scheme's builtin equality predicate.
Any functionality provided in terms of eq?
, eqv?
, equal?
is also
available using a clientprovided equality predicate.
These procedures are not generic as between ordinary pairs/lists and immutable pairs/lists; they are specific to immutable lists. Like Olin, I prefer to keep the library simple and focused. However, there are a few conversions between mutable and immutable lists provided.
Scheme does not properly have a list type, just as C does not have a string type. Rather, Scheme has a binarytuple type, from which one can build binary trees. There is an interpretation of Scheme values that allows one to treat these trees as lists. The same interpretation is applied to immutable pairs.
Because the empty list, written as ()
, is already immutable, it is shared between mutable and immutable lists as the termination marker. It is the only Scheme object that is both a mutable list and an immutable list.
Users should note that dotted lists, whether mutable or immutable, are not commonly
used, and are considered by many Scheme programmers to be an ugly artifact of
Scheme's lack of a true list type.
Dotted ilists are not fully supported by this SRFI. Most procedures are
defined only on proper ilists — that is, ()
terminated ilists. The
procedures that will also handle dotted ilists are specifically
marked. While this design decision restricts the domain of possible arguments
one can pass to these procedures, it has the benefit of allowing the
procedures to catch the error cases where programmers inadvertently pass
scalar values to an ilist procedure by accident,
e.g., by switching the arguments to a procedure call.
The various Scheme standards permit, but do not require,
Scheme implementations to treat quoted pairs and lists as unchangeable.
Thus whereas the expression
(let ((foo (list 1 2 3))) (setcar! foo 10) foo)
evaluates to (10 2 3)
, the value of
(let ((foo '(1 2 3))) (setcar! foo 10) foo)
is not portable, and is in fact an error.
However, such pairs are the same type as mutable pairs:
they answer #t
to pair?
and #f
to ipair?
.
This SRFI recommends that
implementations that provide both this SRFI and
immutable quotations should cause quotations
to return the same immutable pairs that this SRFI describes.
This means that the standard Scheme pair and list operations,
as well as libraries like SRFI 1 which are built on them,
should accept both mutable and immutable pairs: thus
(car (ilist 1 2))
should evaluate to 1
.
This SRFI further recommends that read
should return mutable
pairs and lists when reading list structure. No recommendation is made about the
behavior of write
, display
, and similar output
procedures on immutable lists.
To make life easier for Scheme programmers, given that many implementations
do not provide immutable quotation, the syntax keyword iq
is
provided as part of this SRFI. It is analogous to quote
,
taking an arbitrary number of literals and constructing an ilist from them,
with any pairs in the literals converted to ipairs. It is useful
for providing constant ipairbased objects.
Note that pairs within literal vectors or other implementationdependent literals
will not be converted. Unfortunately, there is no ilist analogue of '
,
so we save keystrokes by using iq
rather than iquote
and omitting the toplevel parentheses.
The templates given below obey the following conventions for procedure formals:
ilist  A proper (() terminated) ilist


dilist  A proper or dotted ilist 
ipair  An immutable pair 
x, y, d, a  Any value 
object, value  Any value 
n, i  A natural number (an integer >= 0) 
proc  A procedure 
pred  A procedure whose return value is treated as a boolean 
=  A boolean procedure taking two arguments 
To interpret the examples, pretend that they are executed on a Scheme that prints immutable pairs and lists with the syntax of mutable ones.
It is an error to pass a dotted ilist to a procedure not defined to accept such an argument.
Added after finalization: Implementers should extend the Scheme
predicate equal?
to descend into immutable pairs in the same
way that it descends into mutable pairs.
ipair
a d > ipair
eqv?
)
from every existing object.
(ipair 'a '()) => (a) (ipair (iq a) (iq b c d)) => ((a) b c d) (ipair "a" (iq b c)) => ("a" b c) (ipair 'a 3) => (a . 3) (ipair (iq a b) 'c) => ((a b ) . c)
ilist
object ... > ilist
(ilist 'a (+ 3 4) 'c) => (a 7 c) (ilist) => ()
xipair
d a > ipair
(lambda (d a) (ipair a d))Of utility only as a value to be conveniently passed to higherorder procedures.
(xipair (iq b c) 'a) => (a b c)The name stands for "eXchanged Immutable PAIR."
ipair*
elt_{1} elt_{2} ... > object
ilist
,
but the last argument provides the tail of the constructed ilist,
returning
(ipair elt_{1} (ipair elt_{2} (ipair ... elt_{n})))
(ipair* 1 2 3 4) => (1 2 3 . 4) (ipair* 1) => 1
makeilist
n [fill] > ilist
(makeilist 4 'c) => (c c c c)
ilisttabulate
n initproc > ilist
(initproc i)
. No guarantee is made about the dynamic
order in which initproc is applied to these indices.
(ilisttabulate 4 values) => (0 1 2 3)
ilistcopy
dilist > dilist
iiota
count [start step] > ilist
(start start+step ... start+(count1)*step)The start and step parameters default to 0 and 1, respectively. This procedure takes its name from the APL primitive.
(iiota 5) => (0 1 2 3 4) (iiota 5 0 0.1) => (0 0.1 0.2 0.3 0.4)
properilist?
x > boolean
ilist?
x > boolean
()
terminated ilist.
More carefully: The empty list is a proper ilist. An ipair whose icdr is a proper ilist is also a proper ilist. Everything else is a dotted ilist. This includes nonipair, non() values (e.g. symbols, numbers, mutable pairs), which are considered to be dotted ilists of length 0.
dottedilist?
x > boolean
(dottedilist? x) = (not (properilist? x))
ipair?
object > boolean
(ipair? (ipair 'a 'b)) => #t (ipair? (iq a b c)) => #t (ipair? (cons 1 2)) => #f (ipair? '()) => #f (ipair? '#(a b)) => #f (ipair? 7) => #f (ipair? 'a) => #f
nullilist?
ilist > boolean
notipair?
x > boolean
(lambda (x) (not (ipair? x)))Provided as a procedure as it can be useful as the termination condition for ilistprocessing procedures that wish to handle all ilists, both proper and dotted.
ilist=
elt= ilist_{1} ... > boolean
(elt= a b)
for a an element of ilist A,
and b an element of ilist B.
In the nary case,
every ilist_{i} is compared to
ilist_{i+1}
(as opposed, for example, to comparing
ilist_{1} to ilist_{i},
for i>1).
If there are no ilist arguments at all,
ilist=
simply returns true.
It is an error to apply ilist=
to anything except proper ilists.
It
cannot reasonably be extended to dotted ilists, as it provides no way to
specify an equality procedure for comparing the ilist terminators.
Note that the dynamic order in which the elt= procedure is
applied to pairs of elements is not specified.
For example, if ilist=
is applied
to three ilists, A, B, and C,
it may first completely compare A to B,
then compare B to C,
or it may compare the first elements of A and B,
then the first elements of B and C,
then the second elements of A and B, and so forth.
The equality procedure must be consistent with eq?
.
That is, it must be the case that
(eq? x y)
=> (elt= x y)
.
eq?
are always ilist=
, as well; implementations may exploit this
fact to "shortcut" the elementbyelement comparisons.
(ilist= eq?) => #t ; Trivial cases (ilist= eq? (iq a)) => #t
icar
ipair > value
icdr
ipair > value
(icar (iq a b c)) => a (icdr (iq a b c)) => (b c) (icar (iq (a) b c d)) => (a) (icdr (iq (a) b c d)) => (b c d) (icar (ipair 1 2)) => 1 (icdr (ipair 1 2)) => 2 (icar '()) => *error* (icdr '()) => *error*
icaar
ipair > value
icadr
ipair > value
:
icdddar
ipair > value
icddddr
ipair > value
icar
and icdr
,
where for example icaddr
could be defined by
(define icaddr (lambda (x) (icar (icdr (icdr x))))).Arbitrary compositions, up to four deep, are provided. There are twentyeight of these procedures in all.
ilistref
ilist i > value
(idrop ilist i)
.)
It is an error if i >= n,
where n is the length of ilist.
(ilistref (iq a b c d) 2) => c
ifirst
ipair > object
isecond
ipair > object
ithird
ipair > object
ifourth
ipair > object
ififth
ipair > object
isixth
ipair > object
iseventh
ipair > object
ieighth
ipair > object
ininth
ipair > object
itenth
ipair > object
car
, cadr
, caddr
, ...
(ithird '(a b c d e)) => c
icar+icdr
ipair > [x y]
(lambda (p) (values (icar p) (icdr p)))This can, of course, be implemented more efficiently by a compiler.
itake
x i > ilist
idrop
x i > object
ilisttail
x i > object
itake
returns the first i elements of ilist x.idrop
returns all but the first i elements of ilist x.ilisttail
is either the same procedure as idrop
or else a procedure with the same behavior.
(itake (iq a b c d e) 2) => (a b) (idrop (iq a b c d e) 2) => (c d e)x may be any value — a proper or dotted ilist:
(itake (ipair 1 (ipair 2 (ipair 3 'd))) => (1 2) (idrop (ipair 1 (ipair 2 (ipair 3 'd))) 2) => (3 . d) (itake (ipair 1 (ipair 2 (ipair 3 'd))) 3) => (1 2 3) (idrop (ipair 1 (ipair 2 (ipair 3 'd))) 3) => dFor a legal i,
itake
and idrop
partition the ilist in a manner which
can be inverted with iappend
:
(iappend (itake x i) (idrop x i)) = x
idrop
is exactly equivalent to performing i icdr operations on x;
the returned value shares a common tail with x.
itakeright
dilist i > object
idropright
dilist i > ilist
itakeright
returns the last i elements of dilist.idropright
returns all but the last i elements of dilist.
(itakeright (iq a b c d e) 2) => (d e) (idropright (iq a b c d e) 2) => (a b c)The returned ilist may share a common tail with the argument ilist.
dilist may be any ilist, either proper or dotted:
(itakeright (iq ipair 1 (ipair 2 (ipair 3 'd))) 2) => (2 3 . d) (idropright (ipair 1 (ipair 2 (ipair 3 'd))) 2) => (1) (itakeright (ipair 1 (ipair 2 (ipair 3 'd))) 0) => d (idropright (ipair 1 (ipair 2 (ipair 3 'd))) 0) => (1 2 3)For a legal i,
itakeright
and idropright
partition the ilist in a manner
which can be inverted with iappend
:
(iappend (itake dilist i) (idrop dilist i)) = dilist
itakeright
's return value is guaranteed to share a common tail with dilist.
isplitat
x i > [ilist object]
isplitat
splits the ilist x
at index i, returning an ilist of the
first i elements, and the remaining tail. It is equivalent
to
(values (itake x i) (idrop x i))
ilast
ipair > object
lastipair
ipair > ipair
lastipair
returns the last ipair in the nonempty
ilist pair.
(ilast (iq a b c)) => c (lastipair (iq a b c)) => (c)
ilength
ilist > integer
ilength
which is not a proper
ilist (()
terminated).
The length of a proper ilist is a nonnegative integer n such that icdr
applied n times to the ilist produces the empty list.
iappend
ilist_{1} ... > ilist
(iappend (iq x) (iq y)) => (x y) (iappend (iq a) (iq b c d)) => (a b c d) (iappend (iq a (b)) (iq (c))) => (a (b) (c))The resulting ilist is always newly allocated, except that it shares structure with the final ilist_{i} argument. This last argument may be any value at all; an improper ilist results if it is not a proper ilist. All other arguments must be proper ilists.
(iappend (iq a b) (ipair 'c 'd)) => (a b c . d) (iappend '() 'a) => a (iappend (iq x y)) => (x y) (iappend) => ()
iconcatenate
ilistofilists > value
iconcatenate
returns
(iapply iappend ilistofilists)or, equivalently,
(ireduceright iappend '() ilistofilists)
Note that some Scheme implementations do not support passing more than a
certain number (e.g., 64) of arguments to an nary procedure.
In these implementations, the (iapply iappend ...)
idiom
would fail when applied to long lists,
but iconcatenate
would continue to function properly.
As with iappend
,
the last element of the input list may be any value at all.
ireverse
ilist > ilist
(ireverse (iq a b c)) => (c b a) (ireverse (iq a (b c) d (e (f)))) => ((e (f)) d (b c) a)
iappendreverse
revhead tail > ilist
iappendreverse
returns
(iappend (ireverse revhead) tail)
.
It is provided because it is a common operation — a common
listprocessing style calls for this exact operation to transfer values
accumulated in reverse order onto the front of another ilist, and because
the implementation is significantly more efficient than the simple
composition it replaces. (But note that this pattern of iterative
computation followed by a reverse can frequently be rewritten as a
recursion, dispensing with the reverse
and iappendreverse
steps, and
shifting temporary, intermediate storage from the heap to the stack,
which is typically a win for reasons of cache locality and eager storage
reclamation.)
izip
ilist_{1} ilist_{2} ... > ilist
(lambda ilists (iapply imap ilist ilists))If
izip
is passed n ilists, it returns an ilist as long as the shortest
of these ilists, each element of which is an nelement ilist comprised
of the corresponding elements from the parameter ilists.
(izip (iq one two three) (iq 1 2 3) (iq odd even odd even odd even odd even)) => ((one 1 odd) (two 2 even) (three 3 odd)) (izip (iq 1 2 3)) => ((1) (2) (3))
iunzip1
ilist > ilist
iunzip2
ilist > [ilist ilist]
iunzip3
ilist > [ilist ilist ilist]
iunzip4
ilist > [ilist ilist ilist ilist]
iunzip5
ilist > [ilist ilist ilist ilist ilist]
iunzip1
takes an ilist of ilists,
where every ilist must contain at least one element,
and returns an ilist containing the initial element of each such ilist.
That is, it returns (imap icar ilists)
.
iunzip2
takes an ilist of ilists, where every ilist must contain at least
two elements, and returns two values: an ilist of the first elements,
and an ilist of the second elements. iunzip3
does the same for the first
three elements of the ilists, and so forth.
(iunzip2 (iq (1 one) (2 two) (3 three))) => (1 2 3) (one two three)
icount
pred ilist_{1} ilist_{2} ... > integer
count
is "iterative" in that it is guaranteed
to apply pred to the ilist elements in a
lefttoright order.
The counting stops when the shortest ilist expires.
(count even? (iq 3 1 4 1 5 9 2 5 6)) => 3 (count < (iq 1 2 4 8) (iq 2 4 6 8 10 12 14 16)) => 3
ifold
kons knil ilist_{1} ilist_{2} ... > value
First, consider the single ilistparameter case. If ilist_{1} = (e_{1} e_{2} ... e_{n}), then this procedure returns
(kons e_{n} ... (kons e_{2} (kons e_{1} knil)) ... )
(ifold kons knil lis) = (ifold kons (kons (icar lis) knil) (icdr lis)) (ifold kons knil '()) = knilExamples:
(ifold + 0 lis) ; Add up the elements of LIS. (ifold ipair '() lis) ; Reverse LIS. (ifold ipair tail revhead) ; See APPENDREVERSE. ;; 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 maxlen) (max maxlen (stringlength 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)
ifoldright
kons knil ilist_{1} ilist_{2} ... > value
First, consider the single ilistparameter case. If ilist_{1} = (e_{1} e_{2} ... e_{n})
,
then this procedure returns
(kons e_{1} (kons e_{2} ... (kons e_{n} knil)))
(ifoldright kons knil lis) = (kons (icar lis) (ifoldright kons knil (icdr lis))) (ifoldright kons knil '()) = knilExamples:
(ifoldright ipair '() lis) ; Copy LIS. ;; Filter the even numbers out of LIS. (ifoldright (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:
(ifoldright ipair* '() (iq a b c) (iq 1 2 3 4 5)) => (a 1 b 2 c 3)
ipairfold
kons knil ilist_{1} ilist_{2} ... > value
fold
, but kons is applied to successive subilists of the
ilists, rather than successive elements — that is, kons is applied to the
ipairs making up the lists, giving this (tail) recursion:
(ipairfold kons knil lis) = (let ((tail (icdr lis)))
(ipairfold kons (kons lis knil) tail))
(ipairfold kons knil '()
) = knil
Example:
(ipairfold ipair '() (iq a b c)) => ((c) (b c) (a b c))
ipairfoldright
kons knil ilist_{1} ilist_{2} ... > value
ifoldright
that ipairfold
holds with ifold
.
Obeys the recursion
(ipairfoldright kons knil lis) =
(kons lis (ipairfoldright kons knil (icdr lis)))
(ipairfoldright kons knil '()
) = knil
Example:
(ipairfoldright ipair '() (iq a b c)) => ((a b c) (b c) (c))
ireduce
f ridentity ilist > value
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))
.
(ifold f ridentity ilist)
.
Note that ridentity is used only in the emptylist 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 nonnegative integers. (ireduce max 0 nums) ; i.e., (iapply max 0 nums)
ireduceright
f ridentity ilist > value
ireduceright
is the foldright variant of ireduce
.
It obeys the following definition:
(ireduceright f ridentity '()) = ridentity (ireduceright f ridentity (iq e_{1})) = (f e_{1} ridentity) = e_{1} (ireduceright f ridentity (iq e_{1} e_{2} ...)) = (f e_{1} (ireduce f ridentity (e_{2} ...)))...in other words, we compute
(ifoldright f ridentity ilist)
.
;; Append a bunch of ilists together. ;; I.e., (iapply iappend ilistofilists) (ireduceright iappend '() ilistofilists)
iunfold
p f g seed [tailgen] > ilist
iunfold
is best described by its basic recursion:
(iunfold p f g seed) = (if (p seed) (tailgen seed) (ipair (f seed) (iunfold p f g (g seed))))
(lambda (x) '())
In other words, we use g to generate a sequence of seed values
iunfold
is the fundamental recursive ilist constructor,
just as ifoldright
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 nullilist? icar icdr lis) ; Copy a proper ilist. ;; Read current input port into an ilist of values. (iunfold eofobject? values (lambda (x) (read)) (read)) ;; Copy a possibly nonproper ilist: (iunfold notipair? icar icdr lis values) ;; Append HEAD onto TAIL: (iunfold nullilist? icar icdr head (lambda (x) tail))Interested functional programmers may enjoy noting that
ifoldright
and iunfold
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
(ifoldright kons knil (iunfold knull? kar kdr x))
= x
(iunfold knull? kar kdr (ifoldright kons knil x))
= x.
iunfoldright
p f g seed [tail] > ilist
iunfoldright
constructs an ilist with the following loop:
(let lp ((seed seed) (lis tail)) (if (p seed) lis (lp (g seed) (ipair (f seed) lis))))
'()
.
In other words, we use g to generate a sequence of seed values
iunfoldright
is the fundamental iterative ilist constructor,
just as ifold
is the
fundamental iterative ilist consumer.
While iunfoldright
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 (iunfoldright zero? (lambda (x) (* x x)) (lambda (x) ( x 1)) 10) ;; Reverse a proper ilist. (iunfoldright nullilist? icar icdr lis) ;; Read current input port into an ilist of values. (iunfoldright eofobject? values (lambda (x) (read)) (read)) ;; (iappendreverse revhead tail) (iunfoldright nullilist? icar icdr revhead tail)Interested functional programmers may enjoy noting that
ifold
and iunfoldright
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
(ifold kons knil (iunfoldright knull? kar kdr x))
= x
(iunfoldright knull? kar kdr (ifold kons knil x))
= x.
imap
proc ilist_{1} ilist_{2} ... > ilist
imap
applies proc elementwise 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)
iforeach
proc ilist_{1} ilist_{2} ... > unspecified
iforeach
are like the arguments to
imap
, but
iforeach
calls proc for its side effects rather
than for its values.
Unlike imap
, iforeach
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 iforeach
is unspecified.
(let ((v (makevector 5))) (iforeach (lambda (i) (vectorset! v i (* i i))) (iq 0 1 2 3 4)) v) => #(0 1 4 9 16)
iappendmap
f ilist_{1} ilist_{2} ... > value
(iapply iappend (imap f ilist_{1} ilist_{2} ...))
(iapply iappend (imap f ilist_{1} ilist_{2} ...))
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:
(iappendmap (lambda (x) (ilist x ( x))) (iq 1 3 8)) => (1 1 3 3 8 8)
imapinorder
f ilist_{1} ilist_{2} ... > ilist
imap
procedure that guarantees to apply f across
the elements of the ilist_{i} arguments in a lefttoright order. This
is useful for mapping procedures that both have side effects and
return useful values.
ipairforeach
f ilist_{1} ilist_{2} ... > unspecific
iforeach
, but f is applied to successive subilists of the argument
ilists. That is, f is applied to the cells of the ilists, rather
than the ilists' elements. These applications occur in lefttoright
order.
(ipairforeach (lambda (ipair) (display ipair) (newline)) (iq a b c)) ==> (a b c) (b c) (c)
ifiltermap
f ilist_{1} ilist_{2} ... > ilist
imap
, but only true values are saved.
(ifiltermap (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.
ifilter
pred ilist > ilist
(ifilter even? (iq 0 7 8 8 43 4)) => (0 8 8 4)
ipartition
pred ilist > [ilist ilist]
(ipartition symbol? (iq one 2 3 four five 6)) => (one four five) (2 3 6)
iremove
pred ilist > ilist
(lambda (pred ilist) (ifilter (lambda (x) (not (pred x))) ilist))The ilist is not disordered — elements that appear in the result ilist occur in the same order as they occur in the argument ilist. The returned ilist may share a common tail with the argument ilist. The dynamic order in which the various applications of pred are made is not specified.
(iremove even? (iq 0 7 8 8 43 4)) => (7 43)
The following procedures all search ilists for a leftmost element satisfying some criteria. This means they do not always examine the entire ilist; thus, there is no efficient way for them to reliably detect and signal an error when passed a dotted ilist. Here are the general rules describing how these procedures work when applied to different kinds of ilists:
In brief, compliant code may not pass a dotted ilist argument to these procedures.
Here are some examples, using the ifind
and iany
procedures as canonical
representatives:
;; Proper ilist — success (ifind even? (iq 1 2 3)) => 2 (iany even? (iq 1 2 3)) => #t ;; proper ilist — failure (ifind even? (iq 1 7 3)) => #f (iany even? (iq 1 7 3)) => #f ;; Failure is error on a dotted ilist. (ifind even? (ipair 1 (ipair 3 'x))) => error (iany even? (ipair 1 (ipair 3 'x))) => error ;; The dotted ilist contains an element satisfying the search. ;; This case is not specified — it could be success, an error, ;; or some third possibility. (ifind even? (ipair 1 (ipair 2 'x))) => error/undefined (iany even? (ipair 1 (ipair 2 'x))) => error/undefined ; success, error or other.
ifind
pred ilist > value
(ifind even? (iq 3 1 4 1 5 9)) => 4Note that
ifind
has an ambiguity in its lookup semantics — if ifind
returns #f
, you cannot tell (in general) if it found a #f
element
that satisfied pred, or if it did not find any element at all. In
many situations, this ambiguity cannot arise — either the ilist being
searched is known not to contain any #f
elements, or the ilist is
guaranteed to have an element satisfying pred. However, in cases
where this ambiguity can arise, you should use ifindtail
instead of
ifind
— ifindtail
has no such ambiguity:
(cond ((ifindtail pred lis) => (lambda (ipair) ...)) ; Handle (icar ipair) (else ...)) ; Search failed.
ifindtail
pred ilist > ipair or false
ifindtail
can be viewed as a generalpredicate variant of the imember
function.
Examples:
(ifindtail even? (iq 3 1 37 8 5 0 0)) => (8 5 0 0) (ifindtail even? (iq 3 1 37 5)) => #f ;; IMEMBER X LIS: (ifindtail (lambda (elt) (equal? x elt)) lis)
Ifindtail
is essentially idropwhile
,
where the sense of the predicate is inverted:
Ifindtail
searches until it finds an element satisfying
the predicate; idropwhile
searches until it finds an
element that doesn't satisfy the predicate.
itakewhile
pred ilist > ilist
(itakewhile even? (iq 2 18 3 10 22 9)) => (2 18)
idropwhile
pred ilist > ilist
(idropwhile even? (iq 2 18 3 10 22 9)) => (3 10 22 9)
ispan
pred ilist > [ilist ilist]
ibreak
pred ilist > [ilist ilist]
ispan
splits the ilist into the longest initial prefix whose
elements all satisfy pred, and the remaining tail.
ibreak
inverts the sense of the predicate:
the tail commences with the first element of the input ilist
that satisfies the predicate.
In other words:
ispan
finds the initial span of elements
satisfying pred,
and ibreak
breaks the ilist at the first element satisfying
pred.
ispan
is equivalent to
(values (itakewhile pred ilist) (idropwhile pred ilist))
(ispan even? (iq 2 18 3 10 22 9)) => (2 18) (3 10 22 9) (ibreak even? (iq 3 1 4 1 5 9)) => (3 1) (4 1 5 9)
iany
pred ilist_{1} ilist_{2} ... > value
If there are n ilist arguments ilist_{1} ... ilist_{n}, then pred must be a procedure taking n arguments and returning a boolean result.
iany
applies pred to the first elements of the ilist_{i} parameters.
If this application returns a true value, iany
immediately returns
that value. Otherwise, it iterates, applying pred to the second
elements of the ilist_{i} parameters, then the third, and so forth.
The iteration stops when a true value is produced or one of the ilists runs
out of values; in
the latter case, iany
returns #f
.
The application of pred to the last element of the
ilists is a tail call.
Note the difference between ifind
and iany
— ifind
returns the element
that satisfied the predicate; iany
returns the true value that the
predicate produced.
Like ievery
, iany
's name does not end with a question mark — this is to
indicate that it does not return a simple boolean (#t
or #f
), but a
general value.
(iany integer? (iq a 3 b 2.7)) => #t (iany integer? (iq a 3.1 b 2.7)) => #f (iany < (iq 3 1 4 1 5) (iq 2 7 1 8 2)) => #t
ievery
pred ilist_{1} ilist_{2} ... > value
If there are n ilist arguments ilist_{1} ... ilist_{n}, then pred must be a procedure taking n arguments and returning a boolean result.
ievery
applies pred to the first elements of the ilist_{i} parameters.
If this application returns false, ievery
immediately returns false.
Otherwise, it iterates, applying pred to the second elements of the
ilist_{i} parameters, then the third, and so forth. The iteration stops
when a false value is produced or one of the ilists runs out of values.
In the latter case, ievery
returns
the true value produced by its final application of pred.
The application of pred to the last element of the ilists
is a tail call.
If one of the ilist_{i} has no elements, ievery
simply returns #t
.
Like iany
, ievery
's name does not end with a question mark — this is to
indicate that it does not return a simple boolean (#t
or #f
), but a
general value.
ilistindex
pred ilist_{1} ilist_{2} ... > integer or false
If there are n ilist arguments ilist_{1} ... ilist_{n}, then pred must be a function taking n arguments and returning a boolean result.
ilistindex
applies pred to the first elements of the ilist_{i} parameters.
If this application returns true, ilistindex
immediately returns zero.
Otherwise, it iterates, applying pred to the second elements of the
ilist_{i} parameters, then the third, and so forth. When it finds a tuple of
ilist elements that cause pred to return true, it stops and returns the
zerobased index of that position in the ilists.
The iteration stops when one of the ilists runs out of values; in this
case, ilistindex
returns #f
.
(ilistindex even? (iq 3 1 4 1 5 9)) => 2 (ilistindex < (iq 3 1 4 1 5 9 2 5 6) (iq 2 7 1 8 2)) => 1 (ilistindex = (iq 3 1 4 1 5 9 2 5 6) (iq 2 7 1 8 2)) => #f
imember
x ilist [=] > ilist
imemq
x ilist > ilist
imemv
x ilist > ilist
(idrop ilist i)
for i less than the length of ilist.
If x does
not occur in ilist, then #f
is returned.
imemq
uses eq?
to compare x
with the elements of ilist,
while imemv
uses eqv?
, and
imember
uses equal?
.
(imemq 'a (iq a b c)) => (a b c) (imemq 'b (iq a b c)) => (b c) (imemq 'a (iq b c d)) => #f (imemq (list 'a) (ilist 'b '(a) 'c)) => #f (imember (list 'a) (ilist 'b '(a) 'c))) => ((a) c) (imemq 101 (iq 100 101 102)) => *unspecified* (imemv 101 (iq 100 101 102)) => (101 102)
The comparison procedure is used to compare the elements e_{i} of ilist to the key x in this way:
(= x e_{i}) ; ilist is (E1 ... En)
(imember 5 ilist <)
Note that fully general ilist searching may be performed with
the ifindtail
and ifind
procedures, e.g.
(ifindtail even? ilist) ; Find the first elt with an even key.
idelete
x ilist [=] > ilist
idelete
uses the comparison procedure =, which defaults to equal?
, to find
all elements of ilist that are equal to x, and deletes them from ilist. The
dynamic order in which the various applications of = are made is not
specified.
The ilist is not disordered — elements that appear in the result ilist occur in the same order as they occur in the argument ilist. The result may share a common tail with the argument ilist.
Note that fully general element deletion can be performed with the iremove
procedures, e.g.:
;; idelete all the even elements from LIS: (iremove even? lis)The comparison procedure is used in this way:
(= x e_{i})
.
That is, x is always the first argument,
and an ilist element is always the
second argument. The comparison procedure will be used to compare each
element of ilist exactly once; the order in which it is applied to the
various e_{i} is not specified. Thus, one can reliably remove all the
numbers greater than five from an ilist with
(idelete 5 ilist <)
ideleteduplicates
ilist [=] > ilist
ideleteduplicates
removes duplicate elements from the
ilist argument.
If there are multiple equal elements in the argument ilist, the result ilist
only contains the first or leftmost of these elements in the result.
The order of these surviving elements is the same as in the original
ilist — ideleteduplicates
does not disorder the ilist (hence it is useful
for "cleaning up" immutable association lists).
The = parameter is used to compare the elements of the ilist; it defaults
to equal?
. If x comes before y in ilist, then the comparison is performed
(= x y)
.
The comparison procedure will be used to compare each pair of elements in
ilist no more than once;
the order in which it is applied to the various pairs is not specified.
Implementations of ideleteduplicates
are allowed to share common tails
between argument and result ilists — for example, if the ilist argument
contains only unique elements, it may simply return exactly
this ilist.
Be aware that, in general, ideleteduplicates
runs in time O(n^{2}) for nelement ilists.
Uniquifying long ilists can be accomplished in O(n lg n) time by sorting
the ilist to bring equal elements together, then using a lineartime
algorithm to remove equal elements. Alternatively, one can use algorithms
based on elementmarking, with lineartime results.
(ideleteduplicates (iq a b a c a b c z)) => (a b c z) ;; Clean up an ialist: (ideleteduplicates (iq (a . 3) (b . 7) (a . 9) (c . 1)) (lambda (x y) (eq? (icar x) (icar y)))) => ((a . 3) (b . 7) (c . 1))
An "immutable association list" (or "ialist") is an ilist of ipairs. The icar of each ipair contains a key value, and the icdr contains the associated data value. They can be used to construct simple lookup tables in Scheme. Note that ialists are probably inappropriate for performancecritical use on large data; in these cases, immutable maps or some other alternative should be employed.
iassoc
key ialist [=] > ipair or #f
iassq
key ialist > ipair or #f
iassv
key ialist > ipair or #f
#f
is returned.
iassq
uses eq?
to compare key
with the icar fields of the ipairs in ialist,
while iassv
uses eqv?
and iassoc
uses equal?
.
(define e (iq (a 1) (b 2) (c 3))) (iassq 'a e) => (a 1) (iassq 'b e) => (b 2) (iassq 'd e) => #f (iassq (ilist 'a) (iq ((a)) ((b)) ((c)))) => #f (iassoc '(a) (ilist '((a)) '((b)) '((c)))) => ((a)) (iassq 5 (iq (2 3) (5 7) (11 13))) => *unspecified* (iassv 5 (iq (2 3) (5 7) (11 13))) => (5 7)
The comparison procedure is used to compare the elements e_{i} of ilist to the key parameter in this way:
(= key (icar e_{i})) ; ilist is (E1 ... En)
(iassoc 5 ialist <)
Note that fully general ialist searching may be performed with
the ifindtail
and ifind
procedures, e.g.
;; Look up the first association in ialist with an even key: (ifind (lambda (a) (even? (icar a))) ialist)
ialistcons
key datum ialist > ialist
(lambda (key datum ialist) (ipair (ipair key datum) ialist))Construct a new ialist entry mapping key > datum onto ialist.
ialistdelete
key ialist [=] > ialist
ialistdelete
deletes all associations from ialist with the given key,
using keycomparison procedure =, which defaults to equal?
.
The dynamic order in which the various applications of = are made is not
specified.
Return values may share common tails with the ialist argument. The ialist is not disordered — elements that appear in the result ialist occur in the same order as they occur in the argument ialist.
The comparison procedure is used to compare the element keys k_{i} of ialist's
entries to the key parameter in this way:
(= key k_{i})
.
Thus, one can reliably remove all entries of ialist whose key is greater
than five with
(ialistdelete 5 ialist <)
These two procedures are analogues of the primitive
sideeffect operations on pairs, setcar!
and setcdr!
.
replaceicar
ipair object > ipair
replaceicdr
ipair object > ipair
These procedures convert between mutable and immutable pair structures.
pair>ipair
pair > ipair
ipair>pair
ipair > pair
list>ilist
flist > dilist
ilist>list
dilist > flist
These procedures return an ilist and a list respectively that have the same elements as the argument. The tails of dotted (i)lists are preserved in the result, which makes the procedures not inverses when the tail of a dotted ilist is a list or vice versa. The empty list is converted to itself.
It is an error to apply list>ilist
to a circular list.
tree>itree
object > object
itree>tree
object > object
These procedures walk a tree of pairs or ipairs respectively and make a deep copy of it, returning an isomorphic tree containing ipairs or pairs respectively. The result may share structure with the argument. If the argument is not of the expected type, it is returned.
These procedures are not inverses in the general case. For example,
a pair of ipairs would be converted by tree>itree
to
an ipair of ipairs, which if converted by itree>tree
would produce a pair of pairs.
gtree>itree
object > object
gtree>tree
object > object
This procedure allows a procedure to be applied to an ilist.
iapply
procedure object ... ilist > object
iapply
procedure is an analogue of apply
whose last
argument is an ilist rather than a list. It is equivalent to
(apply
procedure object ... (ilist>list
ilist))
,
but may be implemented more efficiently.
ipaircomparator
ipaircomparator
object is a SRFI114 comparator suitable for comparing ipairs.
Note that it is not a procedure.
It compares pairs using defaultcomparator
on their cars. If the cars are not equal, that value is returned. If they are equal, defaultcomparator
is used on their cdrs and that value is returned.
ilistcomparator
ilistcomparator
object is a SRFI114 comparator suitable for comparing ilists.
Note that it is not a procedure.
It compares ilists lexicographically, as follows:
defaultcomparator
, then the result is the result of that comparison. Otherwise, the icdrs are compared using ilistcomparator
.makeilistcomparator
comparator > comparator
makeilistcomparator
procedure returns a comparator suitable for comparing ilists
using elementcomparator to compare the elements.
makeimproperilistcomparator
comparator > comparator
makeimproperilistcomparator
procedure returns a comparator that compares arbitrary objects as follows: the empty list precedes all ipairs, which precede all other objects. Ipairs are compared as if with (makeipaircomparator
comparator
comparator)
. All other objects are compared using comparator.
makeicarcomparator
comparator > comparator
makeicarcomparator
procedure returns a comparator that compares ipairs on their icars alone using comparator.
makeicdrcomparator
comparator > comparator
makeicdrcomparator
procedure returns a comparator that compares ipairs on their icdrs alone using comparator.
The sample implementation of this SRFI is derived from the sample implementation of SRFI 1. It depends on SRFI 9 (or R7RS) records. The five files in the implementation are as follows:
ilistsimpl.scm
is a modified version of the SRFI 1 implementation.ilistsbase.scm
provides the definition of ipair records as well as additional procedures that are required by this SRFI.ilists.sld
is an R7RS library.ilists.scm
is a Chicken library.iliststest.scm
is a set of tests using the Chicken test
egg, which is also available in Chibi as the R7RS library (chibi test)
.Without the work of Olin Shivers on SRFI 1, this SRFI would not exist. Everyone acknowledged there is transitively acknowledged here. This is not to imply that either Olin or anyone else necessarily endorses the final results, of course.
Copyright (C) John Cowan 2014. All Rights Reserved.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.