Title

Immutable List Library

Author

John Cowan
http://www.ccil.org/~cowan
cowan@ccil.org

Status

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 srfi-116@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

Table of contents

Abstract

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, set-mcar!, set-mcdr!. 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.

Rationale

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 SRFI-1 that treats the linear-update procedures (with !) as identical to their functional counterparts, as Racket does? The main answer is that this approach breaks R5RS and R7RS-small. All the data structures in these versions of Scheme are inherently mutable, and portable code is allowed to depend on that property.

R6RS segregates set-car! and set-cdr! 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 R6RS 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:

Note: In the prose, immutable pairs and lists are known as ipairs and ilists throughout.

Procedure Index

Here is a short list of the procedures provided by this SRFI.

Constructors
ipair ilist
xipair ipair* make-ilist ilist-tabulate
ilist-copy iiota
Predicates
ipair?
proper-ilist?/ilist? dotted-ilist?
not-ipair? null-ilist?
ilist=
Selectors
icar icdr ... icddadr icddddr ilist-ref
ifirst isecond ithird ifourth ififth isixth iseventh ieighth ininth itenth
icar+icdr
itake       idrop/ilist-tail
itake-right idrop-right
isplit-at
ilast last-ipair
Miscellaneous: length, append, concatenate, reverse, zip & count
ilength
iappend  iconcatenate  ireverse  iappend-reverse
izip iunzip1 iunzip2 iunzip3 iunzip4 iunzip5
icount
Fold, unfold & map
imap        ifor-each
ifold       iunfold        ipair-fold       ireduce
ifold-right iunfold-right  ipair-fold-right ireduce-right
iappend-map ipair-for-each ifilter-map      imap-in-order
Filtering & partitioning
ifilter  ipartition  iremove

Searching
imember imemq imemv
ifind         ifind-tail
iany ievery
ilist-index
itake-while   idrop-while
ispan ibreak
Deleting
idelete       idelete-duplicates

Immutable association lists
iassoc iassq iassv
ialist-cons  ialist-delete
Replacement
replace-icar replace-icdr
Conversion
pair->ipair  ipair->pair
list->ilist  ilist->list
tree->itree  itree->tree
gtree->itree gtree->tree
Procedure application
iapply
Comparators
ipair-comparator        ilist-comparator
make-ilist-comparator   make-improper-ilist-comparator
make-icar-comparator    make-icdr-comparator

General discussion

A set of general criteria guided the design of the SRFI-1 library that underlies this library. They are reproduced here.

List-filtering 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 list-filtering 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, ifind-tail, ifor-each, iany and ievery commit to a left-to-right traversal order of their argument list.

However, constructors, such as ilist-tabulate and the mapping procedures (iappend-map, ipair-for-each, ifilter-map, imap-in-order), 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 built-in equality predicate. Any functionality provided in terms of eq?, eqv?, equal? is also available using a client-provided 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.

Improper Lists

Scheme does not properly have a list type, just as C does not have a string type. Rather, Scheme has a binary-tuple 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.

Quotation

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))) (set-car! foo 10) foo) evaluates to (10 2 3), the value of (let ((foo '(1 2 3))) (set-car! foo 10) foo) is not portable, and is in fact an error.

This SRFI recommends that implementations that provide both this SRFI and unchangeable 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.

If this SRFI is implemented on a Scheme system which does in fact disallow the modification of quoted pairs, then this SRFI recommends that the procedures given here accept such quoted pairs as arguments where ipairs are expected.

In addition, this SRFI recommends that (where feasible) procedures that expect either pairs or ipairs as arguments accept both pairs and ipairs. If this implementation option is chosen, then if such a call is defined to return newly allocated pairs (such as cons), then it returns ordinary pairs, but if it is defined to return newly allocated ipairs (such as icons), then it returns ipairs. However, if it returns existing objects, they will be pairs or ipairs or other objects as the case may be.

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 partly 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 ipair-based objects. Note that pairs within literal vectors or other implementation-dependent 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 top-level parentheses.

The procedures

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.

Constructors

ipair a d -> ipair
The primitive constructor. Returns a newly allocated ipair whose icar is a and whose icdr is d. The ipair is guaranteed to be different (in the sense of 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
Returns a newly allocated ilist of its arguments.
(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 higher-order procedures.
(xipair (iq b c) 'a) => (a b c)
The name stands for "eXchanged Immutable PAIR."
ipair* elt1 elt2 ... -> object
Like ilist, but the last argument provides the tail of the constructed ilist, returning
(ipair elt1 (ipair elt2 (ipair ... eltn)))
(ipair* 1 2 3 4) => (1 2 3 . 4)
(ipair* 1) => 1
make-ilist n [fill] -> ilist
Returns an n-element ilist, whose elements are all the value fill. If the fill argument is not given, the elements of the ilist may be arbitrary values.
(make-ilist 4 'c) => (c c c c)
ilist-tabulate n init-proc -> ilist
Returns an n-element ilist. Element i of the ilist, where 0 <= i < n, is produced by (init-proc i). No guarantee is made about the dynamic order in which init-proc is applied to these indices.
(ilist-tabulate 4 values) => (0 1 2 3)
ilist-copy dilist -> dilist
Copies the spine of the argument, including the ilist tail.
iiota count [start step] -> ilist
Returns an ilist containing the elements
(start start+step ... start+(count-1)*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)

Predicates

proper-ilist? x -> boolean
ilist? x -> boolean
These identifiers are bound either to the same procedure, or to procedures of equivalent behavior. In either case, true is returned iff x is a proper ilist — a ()-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 non-ipair, non-() values (e.g. symbols, numbers, mutable pairs), which are considered to be dotted ilists of length 0.

dotted-ilist? x -> boolean
True if x is a finite, non-nil-terminated ilist. That is, there exists an n >= 0 such that icdrn(x) is neither an ipair nor (). This includes non-ipair, non-() values (e.g. symbols, numbers), which are considered to be dotted ilists of length 0.
(dotted-ilist? x) = (not (proper-ilist? x))
ipair? object -> boolean
Returns #t if object is an ipair; otherwise, #f.
(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
null-ilist? ilist -> boolean
Ilist is a proper ilist. This procedure returns true if the argument is the empty list (), and false otherwise. It is an error to pass this procedure a value which is not a proper ilist. This procedure is recommended as the termination condition for ilist-processing procedures that are not defined on dotted ilists.
not-ipair? x -> boolean
(lambda (x) (not (ipair? x)))
Provided as a procedure as it can be useful as the termination condition for ilist-processing procedures that wish to handle all ilists, both proper and dotted.
ilist= elt= ilist1 ... -> boolean
Determines ilist equality, given an element-equality procedure. Proper ilist A equals proper ilist B if they are of the same length, and their corresponding elements are equal, as determined by elt=. If the element-comparison procedure's first argument is from ilisti, then its second argument is from ilisti+1, i.e. it is always called as (elt= a b) for a an element of ilist A, and b an element of ilist B.

In the n-ary case, every ilisti is compared to ilisti+1 (as opposed, for example, to comparing ilist1 to ilisti, 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).
Note that this implies that two ilists which are eq? are always ilist=, as well; implementations may exploit this fact to "short-cut" the element-by-element comparisons.
(ilist= eq?) => #t       ; Trivial cases
(ilist= eq? (iq a)) => #t

Selectors

icar ipair -> value
icdr ipair -> value
These procedures return the contents of the icar and icdr field of their argument, respectively. Note that it is an error to apply them to the empty ilist.
(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
These procedures are compositions of 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 twenty-eight of these procedures in all.
ilist-ref ilist i -> value
Returns the ith element of ilist. (This is the same as the icar of (idrop ilist i).) It is an error if i >= n, where n is the length of ilist.
(ilist-ref (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
Synonyms for car, cadr, caddr, ...
(ithird '(a b c d e)) => c
icar+icdr ipair -> [x y]
The fundamental ipair deconstructor:
(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
ilist-tail x i -> object
itake returns the first i elements of ilist x.
idrop returns all but the first i elements of ilist x.
ilist-tail 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) => d
For 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.
itake-right dilist i -> object
idrop-right dilist i -> ilist
itake-right returns the last i elements of dilist.
idrop-right returns all but the last i elements of dilist.
(itake-right (iq a b c d e) 2) => (d e)
(idrop-right (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:

(itake-right (iq ipair 1 (ipair 2 (ipair 3 'd))) 2) => (2 3 . d)
(idrop-right (ipair 1 (ipair 2 (ipair 3 'd))) 2)    => (1)
(itake-right (ipair 1 (ipair 2 (ipair 3 'd))) 0)    => d
(idrop-right (ipair 1 (ipair 2 (ipair 3 'd))) 0)    => (1 2 3)
For a legal i, itake-right and idrop-right partition the ilist in a manner which can be inverted with iappend:
(iappend (itake dilist i) (idrop dilist i)) = dilist
itake-right's return value is guaranteed to share a common tail with dilist.
isplit-at  x i -> [ilist object]
isplit-at 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
last-ipair ipair -> ipair
Returns the last element of the non-empty, possibly dotted, ilist ipair. last-ipair returns the last ipair in the non-empty ilist pair.
(ilast (iq a b c))      => c
(last-ipair (iq a b c)) => (c)

Miscellaneous: length, append, concatenate, reverse, zip & count

ilength  ilist -> integer
Returns the length of its argument. It is an error to pass a value to ilength which is not a proper ilist (()-terminated).

The length of a proper ilist is a non-negative integer n such that icdr applied n times to the ilist produces the empty list.

iappend  ilist1 ... -> ilist
Returns an ilist consisting of the elements of ilist1 followed by the elements of the other ilist parameters.
(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 ilisti 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  ilist-of-ilists -> value
Appends the elements of its argument together. That is, iconcatenate returns
(iapply iappend ilist-of-ilists)
or, equivalently,
(ireduce-right iappend '() ilist-of-ilists)

Note that some Scheme implementations do not support passing more than a certain number (e.g., 64) of arguments to an n-ary 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
Returns a newly allocated ilist consisting of the elements of ilist in reverse order.
(ireverse (iq a b c)) =>  (c b a)
(ireverse (iq a (b c) d (e (f))))
    =>  ((e (f)) d (b c) a)
iappend-reverse  rev-head tail -> ilist
iappend-reverse returns (iappend (ireverse rev-head) tail). It is provided because it is a common operation — a common list-processing 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 iappend-reverse 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 ilist1 ilist2 ... -> 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 n-element 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 ilist1 ilist2 ... -> integer
pred is a procedure taking as many arguments as there are ilists and returning a single value. It is applied element-wise to the elements of the ilists, and a count is tallied of the number of elements that produce a true value. This count is returned. count is "iterative" in that it is guaranteed to apply pred to the ilist elements in a left-to-right 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

Fold, unfold & map

ifold kons knil ilist1 ilist2 ... -> value
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)
ifold-right kons knil ilist1 ilist2 ... -> value
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)
ipair-fold kons knil ilist1 ilist2 ... -> value
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))
ipair-fold-right kons knil ilist1 ilist2 ... -> value
Holds 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 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:
If ilist = (), return ridentity;
Otherwise, return (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 f ridentity ilist -> value
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 p f g seed [tail-gen] -> ilist
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))))
p
Determines when to stop unfolding.
f
Maps each seed value to the corresponding ilist element.
g
Maps each seed value to next seed value.
seed
The "state" value for the unfold.
tail-gen
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 and (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 p f g seed [tail] -> ilist
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))))
p
Determines when to stop unfolding.
f
Maps each seed value to the corresponding ilist element.
g
Maps each seed value to next seed value.
seed
The "state" value for the unfold.
tail
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 and (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.
imap proc ilist1 ilist2 ... -> ilist
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)

ifor-each proc ilist1 ilist2 ... -> unspecified
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)

iappend-map  f ilist1 ilist2 ... -> value
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)
imap-in-order f ilist1 ilist2 ... -> ilist
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.

ipair-for-each f ilist1 ilist2 ... -> unspecific
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)
ifilter-map f ilist1 ilist2 ... -> ilist
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.

Filtering & partitioning

ifilter pred ilist -> ilist
Return all the elements of ilist that satisfy predicate pred. 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.
(ifilter even? (iq 0 7 8 8 43 -4)) => (0 8 8 -4)
ipartition pred ilist -> [ilist ilist]
Partitions the elements of ilist with predicate pred, and returns two values: the ilist of in-elements and the ilist of out-elements. The ilist is not disordered — elements occur in the result ilists in the same order as they occur in the argument ilist. The dynamic order in which the various applications of pred are made is not specified. One of the returned ilists may share a common tail with the argument ilist.
(ipartition symbol? (iq one 2 3 four five 6)) =>
    (one four five)
    (2 3 6)
iremove pred ilist -> ilist
Returns ilist without the elements that satisfy predicate pred:
(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)

Searching

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:

Proper ilists:
The standard, canonical behavior happens in this case.
Dotted ilists:
It is an error to pass these procedures a dotted ilist that does not contain an element satisfying the search criteria. That is, it is an error if the procedure has to search all the way to the end of the dotted ilist. However, this SRFI does not specify anything at all about the behavior of these procedures when passed a dotted ilist containing an element satisfying the search criteria. It may finish successfully, signal an error, or perform some third action. Different implementations may provide different functionality in this case; code which is compliant with this SRFI may not rely on any particular behavior. Future SRFIs may refine this SRFI to define specific behavior in this case.

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
Return the first element of ilist that satisfies predicate pred; false if no element does.
(ifind even? (iq 3 1 4 1 5 9)) => 4
Note 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 ifind-tail instead of ifindifind-tail has no such ambiguity:
(cond ((ifind-tail pred lis) => (lambda (ipair) ...)) ; Handle (icar ipair)
      (else ...)) ; Search failed.
ifind-tail pred ilist -> ipair or false
Return the first ipair of ilist whose icar satisfies pred. If no ipair does, return false.

ifind-tail can be viewed as a general-predicate variant of the imember function.

Examples:

(ifind-tail even? (iq 3 1 37 -8 -5 0 0)) => (-8 -5 0 0)
(ifind-tail even? (iq 3 1 37 -5)) => #f

;; IMEMBER X LIS:
(ifind-tail (lambda (elt) (equal? x elt)) lis)

Ifind-tail is essentially idrop-while, where the sense of the predicate is inverted: Ifind-tail searches until it finds an element satisfying the predicate; idrop-while searches until it finds an element that doesn't satisfy the predicate.

itake-while  pred ilist -> ilist
Returns the longest initial prefix of ilist whose elements all satisfy the predicate pred.

(itake-while even? (iq 2 18 3 10 22 9)) => (2 18)
idrop-while pred ilist -> ilist
idrops the longest initial prefix of ilist whose elements all satisfy the predicate pred, and returns the rest of the ilist.
(idrop-while 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 (itake-while pred ilist)
        (idrop-while 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 ilist1 ilist2 ... -> value
Applies the predicate across the ilists, returning true if the predicate returns true on any application.

If there are n ilist arguments ilist1 ... ilistn, then pred must be a procedure taking n arguments and returning a boolean result.

iany applies pred to the first elements of the ilisti parameters. If this application returns a true value, iany immediately returns that value. Otherwise, it iterates, applying pred to the second elements of the ilisti 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 ianyifind 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 ilist1 ilist2 ... -> value
Applies the predicate across the ilists, returning true if the predicate returns true on every application.

If there are n ilist arguments ilist1 ... ilistn, then pred must be a procedure taking n arguments and returning a boolean result.

ievery applies pred to the first elements of the ilisti parameters. If this application returns false, ievery immediately returns false. Otherwise, it iterates, applying pred to the second elements of the ilisti 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 ilisti 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.

ilist-index pred ilist1 ilist2 ... -> integer or false
Return the index of the leftmost element that satisfies pred.

If there are n ilist arguments ilist1 ... ilistn, then pred must be a function taking n arguments and returning a boolean result.

ilist-index applies pred to the first elements of the ilisti parameters. If this application returns true, ilist-index immediately returns zero. Otherwise, it iterates, applying pred to the second elements of the ilisti 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 zero-based index of that position in the ilists.

The iteration stops when one of the ilists runs out of values; in this case, ilist-index returns #f.

(ilist-index even? (iq 3 1 4 1 5 9)) => 2
(ilist-index < (iq 3 1 4 1 5 9 2 5 6) (iq 2 7 1 8 2)) => 1
(ilist-index = (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
These procedures return the first sub-ilist of ilist whose icar is x, where the sub-ilists of ilist are the non-empty ilists returned by (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 ei of ilist to the key x in this way:

(= x ei) ; ilist is (E1 ... En)
That is, the first argument is always x, and the second argument is one of the ilist elements. Thus one can reliably find the first element of ilist that is greater than five with (imember 5 ilist <)

Note that fully general ilist searching may be performed with the ifind-tail and ifind procedures, e.g.

(ifind-tail even? ilist) ; Find the first elt with an even key.

Deletion

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 ei). 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 ei is not specified. Thus, one can reliably remove all the numbers greater than five from an ilist with (idelete 5 ilist <)
idelete-duplicates  ilist [=] -> ilist
idelete-duplicates 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 — idelete-duplicates 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 idelete-duplicates 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, idelete-duplicates runs in time O(n2) for n-element 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 linear-time algorithm to remove equal elements. Alternatively, one can use algorithms based on element-marking, with linear-time results.

(idelete-duplicates (iq a b a c a b c z)) => (a b c z)

;; Clean up an ialist:
(idelete-duplicates (iq (a . 3) (b . 7) (a . 9) (c . 1))
                   (lambda (x y) (eq? (icar x) (icar y))))
    => ((a . 3) (b . 7) (c . 1))

Immutable association lists

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 look-up tables in Scheme. Note that ialists are probably inappropriate for performance-critical 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
ialist must be an immutable association list — an ilist of ipairs. These procedures find the first ipair in ialist whose icar field is key, and returns that ipair. If no ipair in ialist has key as its icar, then #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 ei of ilist to the key parameter in this way:

(= key (icar ei)) ; ilist is (E1 ... En)
That is, the first argument is always key, and the second argument is one of the ilist elements. Thus one can reliably find the first entry of ialist whose key is greater than five with (iassoc 5 ialist <)

Note that fully general ialist searching may be performed with the ifind-tail and ifind procedures, e.g.

;; Look up the first association in ialist with an even key:
(ifind (lambda (a) (even? (icar a))) ialist)
ialist-cons key datum ialist -> ialist
(lambda (key datum ialist) (ipair (ipair key datum) ialist))
Construct a new ialist entry mapping key -> datum onto ialist.
ialist-delete  key ialist [=] -> ialist
ialist-delete deletes all associations from ialist with the given key, using key-comparison 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 ki of ialist's entries to the key parameter in this way: (= key ki). Thus, one can reliably remove all entries of ialist whose key is greater than five with (ialist-delete 5 ialist <)

Replacement

These two procedures are analogues of the primitive side-effect operations on pairs, set-car! and set-cdr!.

replace-icar ipair object -> ipair
This procedure returns an ipair with object in the icar field and the icdr of ipair in the icdr field.
replace-icdr ipair object -> ipair
This procedure returns an ipair with object in the icdr field and the icar of ipair in the icar field.

Conversion

These procedures convert between mutable and immutable pair structures.

pair->ipair pair -> ipair
ipair->pair ipair -> pair
These procedures, which are inverses, return an ipair and a pair respectively that have the same (i)car and (i)cdr fields as the argument.
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
These procedures walk a generalized tree consisting of pairs, ipairs, or a combination of both, and make a deep copy of it, returning an isomorphic tree containing only ipairs or pairs respectively. The result may share structure with the argument. If the argument is neither a pair nor an ipair, it is returned.

Procedure Application

This procedure allows a procedure to be applied to an ilist.

iapply procedure object ... ilist -> object
The 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.

Comparators

ipair-comparator
The ipair-comparator object is a SRFI-114 comparator suitable for comparing ipairs. Note that it is not a procedure. It compares pairs using default-comparator on their cars. If the cars are not equal, that value is returned. If they are equal, default-comparator is used on their cdrs and that value is returned.
ilist-comparator
The ilist-comparator object is a SRFI-114 comparator suitable for comparing ilists. Note that it is not a procedure. It compares ilists lexicographically, as follows:
make-ilist-comparator comparator -> comparator
The make-ilist-comparator procedure returns a comparator suitable for comparing ilists using element-comparator to compare the elements.
make-improper-ilist-comparator comparator -> comparator
The make-improper-ilist-comparator 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 (make-ipair-comparator comparator comparator). All other objects are compared using comparator.
make-ipair-comparator icar-comparator icdr-comparator -> comparator
Returns a comparator that compares ipairs first on their icars using icar-comparator. If the icars are equal, it compares the icdrs using icdr-comparator.
make-icar-comparator comparator -> comparator
The make-icar-comparator procedure returns a comparator that compares ipairs on their icars alone using comparator.
make-icdr-comparator comparator -> comparator
The make-icdr-comparator procedure returns a comparator that compares ipairs on their icdrs alone using comparator.

Sample Implementation

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:

Acknowledgements

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.

References & links

This document, in HTML:
https://srfi.schemers.org/srfi-116/srfi-116.html
Source code for the reference implementation:
https://srfi.schemers.org/srfi-116/srfi-116.tgz
Archive of SRFI-116 discussion-list email:
https://srfi-email.schemers.org/srfi-116/
SRFI web site:
https://srfi.schemers.org/

Copyright

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.


Editor: Mike Sperber