In addition to the naming conventions used in the rest of the Report, Add xref. [wcm] this library uses the following names to indicate the types of procedure arguments and return values:
proper or circular list
finite proper or improper list
boolean procedure taking two arguments
Equivalent to
(lambda (obj1 obj2) (cons obj2 obj1))Of utility only as a value to be conveniently passed to higher-order procedures.
(xcons '(b c) 'a)⇒(a b c)
Like list, but the last argument provides the tail of the constructed list, returning
(cons obj1 (cons obj2 (cons … objn)))(cons* 1 2 3 4)⇒(1 2 3 . 4)
(cons* 1)⇒1
Returns a k-element list. Element of the list, where , is produced by (proc i). No guarantee is made about the dynamic order in which init-proc is applied to these indices.
(list-tabulate 4 values)⇒(0 1 2 3)
Constructs a circular list of the elements.
(circular-list 'z 'q)⇒(z q z q z q …)
Returns a list containing the elements
The start and step parameters default to 0 and 1, respectively.
(iota 5)⇒(0 1 2 3 4)
(iota 5 0 -0.1)⇒(0 -0.1 -0.2 -0.3 -0.4)
True if obj is a circular list. A circular list is a value such that for every , is a pair.
True if obj is a finite improper list.
Returns true if list is the empty list, and false otherwise.
SRFI 1 includes the following recommendation, which is probably bogus: 'This procedure is recommended as the termination condition for list-processing procedures that are not defined on dotted lists.' Is anyone actually using 'null-list?' like this? [wcm]Equivalent to
(lambda (x) (not (pair? x)))Provided as a procedure as it can be useful as the termination condition for list-processing procedures that wish to handle all finite lists, both proper and dotted.
Determines list equality, given an element-equality procedure. Proper list equals proper list 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 listi, then its second argument is from listi+1, i.e. it is always called as (elt=?ab) for an element of list and an element of list .
In the -ary case, every listi is compared to listi+1 (as opposed, for example, to comparing list1 to every listi, for ). If there are no list arguments at all, list= simply returns true.
It is an error to apply list= to anything except proper lists. While implementations may choose to extend it to circular lists, note that it cannot reasonably be extended to dotted lists, as it provides no way to specify an equality procedure for comparing the list terminators.
Note that the dynamic order in which the elt=? procedure is applied to pairs of elements is not specified. For example, if list= is applied to three lists, , , and , it may first completely compare to , then compare to , or it may compare the first elements of and , then the first elements of and , then the second elements of and , and so forth.
The equality procedure must be consistent with eq?. That is, it must be the case that (eq? x y) implies (elt=? x y).
Note that this implies that two lists which are eq? are always list=, as well; implementations may exploit this fact to “short-cut” the element-by-element comparisons.
;; Trivial cases: (list= eq?)⇒#t
(list= eq? '(a))⇒#t
Synonyms for car, cadr, caddr, …
(third '(a b c d e))⇒c
Equivalent to
(lambda (p) (values (car p) (cdr p)))but may be implemented more efficiently.
take returns the first k elements of list obj.
If the argument is a list of non-zero length, take is guaranteed to return a freshly-allocated list, even in the case where the entire list is taken, e.g. (take lis (length lis)).
(take '(a b c d e) 2)⇒(a b)
(take '(1 2 3 . d) 2)⇒(1 2)
(take '(1 2 3 . d) 3)⇒(1 2 3)
drop returns all but the first k elements of list obj.
drop is exactly equivalent to performing k cdr operations on obj; the returned value shares a common tail with obj.
(drop '(a b c d e) 2)⇒(c d e)
(drop '(1 2 3 . d) 2)⇒(3 . d)
(drop '(1 2 3 . d) 3)⇒d
take-right returns the last k elements of flist.
take-right’s return value is guaranteed to share a common tail with flist.
(take-right '(a b c d e) 2)⇒(d e)
(take-right '(1 2 3 . d) 2)⇒(2 3 . d)
(take-right '(1 2 3 . d) 0)⇒d
drop-right returns all but the last k elements of flist.
drop-right is guaranteed to return a freshly-allocated list, even in the case where nothing is dropped, e.g. (drop-right lis 0).
(drop-right '(a b c d e) 2)⇒(a b c)
(drop-right '(1 2 3 . d) 2)⇒(1)
(drop-right '(1 2 3 . d) 0)⇒(1 2 3)
take! is a linear-update variant of take: it is allowed, but not required, to alter obj to produce the result.
If obj is circular, take! may return a shorter-than-expected list:
(take! (circular-list 1 3 5) 8)⇒(1 3)
(take! (circular-list 1 3 5) 8)⇒(1 3 5 1 3 5 1 3)
drop-right! is a linear-update variant of drop-right: it is allowed, but not required, to alter flist to produce the result.
split-at splits obj at index k, returning a list of the first k elements, and the remaining tail. It is equivalent to
(values (take obj k) (drop obj k))(split-at '(a b c d e f g h) 3)⇒(a b c) (d e f g h)
split-at! is the linear-update variant of split-at. It is allowed, but not required, to alter obj to produce the result.
Returns the last pair of pair.
(last-pair '(a b c))⇒(c)
Returns the length of clist if it is a finite proper list. Otherwise, returns #f.
append! is a linear-update variant of append — it is allowed, but not required, to alter cons cells in the argument lists to construct the result list. The last argument is never altered; the result list shares structure with this parameter.
Appends the elements of listtogether. That is, concatenate returns the value of
(apply append list).As with append and append!, the last element of the input list may be any value at all.
Rationale: Some Scheme implementations do not support passing more than a certain number (e.g., 64) of arguments to an -ary procedure. In these implementations, the (apply append …) idiom would fail when applied to long lists, but concatenate would continue to function properly.
concatenate! is the linear-update variant of concatenate, defined in terms of append! instead of append.
reverse! is the linear-update variant of reverse. It is permitted, but not required, to alter list’s cons cells to produce the reversed list.
Returns the value of
(append (reverse list) obj).Rationale: append-reverse 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 list, and because the implementation is significantly more efficient than the simple composition it replaces.
append-reverse! is the linear-update variant of append-reverse. It is allowed, but not required, to alter list’s cons cells to construct the result.
If zip is passed lists, it returns a list as long as the shortest of these lists, each element of which is an -element list comprised of the corresponding elements from the parameter lists. At least one of the argument lists must be finite.
(zip '(one two three) '(1 2 3) '(odd even odd even odd even odd even))⇒((one 1 odd) (two 2 even) (three 3 odd))
(zip '(1 2 3))⇒((1) (2) (3))
unzip1 takes a list of lists, where every list must contain at least one element, and returns a list containing the initial element of each such list. That is, it returns (map car lists). unzip2 takes a list of lists, where every list must contain at least two elements, and returns two values: a list of the first elements, and a list of the second elements. unzip3 does the same for the first three elements of the lists, and so forth.
(unzip2 '((1 one) (2 two) (3 three)))⇒(1 2 3) (one two three)
proc is a procedure taking as many arguments as there are lists and returning a single value. It is applied element-wise to the elements of the clists, and a count is tallied of the number of elements that produce a true value. This count is returned. count is guaranteed to apply proc to the clist elements in a left-to-right order. At least one of the clists must be finite. The counting stops when the shortest list expires.
(count even? '(3 1 4 1 5 9 2 5 6))⇒3
(count < '(1 2 4 8) '(2 4 6 8 10 12 14 16))⇒3
(count < '(3 1 4 1) (circular-list 1 10))⇒2
First, consider the single list-parameter case. If clist1 equals (e1 e2 … en), then this procedure returns
(kons en … (kons e1 knil)) … )That is, it obeys the (tail) recursion
There are two rows here, so don't delete the literal newline. I'm not so sure about the bare scheme-listing, though. [wcm](fold kons knil lis) = (fold kons (kons (car lis) knil) (cdr lis))
(fold kons knil '()) = knilIf clist arguments are provided, then the kons function must take parameters: one element from each list, and the “seed” or fold state, which is initially knil. The fold operation terminates when the shortest list runs out of values. At least one of the clist arguments must be finite.
(fold + 0 lis) ; Add up the elements of lis.
(fold cons '() lis) ; Reverse list.
(fold cons tail rev-head) ; See append-reverse.
;; How many symbols in lis?
(fold (lambda (x count) (if (symbol? x) (+ count 1) count))
0
lis)
;; Length of the longest string in lis:
(fold (lambda (s max-len) (max max-len (string-length s)))
0
lis)(fold cons* '() '(a b c) '(1 2 3 4 5))⇒(c 3 b 2 a 1)
First, consider the single list-parameter case. If clist1 equals (e1 e2 … en), then this procedure returns
(kons e1 (konse2 … (konsenknil)))That is, it obeys the recursion
There are two rows here, so don't delete the literal newline. I'm not so sure about the bare scheme-listing, though. [wcm](fold-right kons knil lis) = (kons (car lis) (fold-right kons knil (cdr lis)))
(fold-right kons knil '()) = knilIf list arguments are provided, then the kons function must take parameters: one element from each list, and the “seed” or fold state, which is initially knil. The fold operation terminates when the shortest list runs out of values. At least one of the clist arguments must be finite.
(fold-right cons '() lis) ; Copy lis.
;; Filter the even numbers out of lis.
(fold-right (lambda (x l) (if (even? x) (cons x l) l)) '() lis))(fold-right cons* '() '(a b c) '(1 2 3 4 5))⇒(a 1 b 2 c 3)
Analogous to fold, but kons is applied to successive sublists of the clists, rather than successive elements — that is, kons is applied to the pairs making up the lists, giving this (tail) recursion:
Two rows, again. Don't delete the literal newline. [wcm](pair-fold konsknillis) = (let ((tail (cdr lis))) (pair-fold kons (kons lis knil) tail))
(pair-fold konsknil'()) = knilAt least one of the clists must be finite.
For finite lists, the kons function may reliably apply set-cdr! to the pairs it is given without altering the sequence of execution.
;;; Destructively reverse a list.
(pair-fold (lambda (pair tail) (set-cdr! pair tail) pair) '() lis)Holds the same relationship with fold-right that pair-fold holds with fold. Obeys the recursion
Two rows, again. Don't delete the literal newline. [wcm](pair-fold-right kons knil lis) = (kons lis (pair-fold-right kons knil (cdr lis)))
(pair-fold-right kons knil '()) = knilAt least one of the clist arguments must be finite.
ridentity should be a “right identity” of the procedure proc — that is, for any value x acceptable to proc,
(proc x ridentity) = x
If list is (), reduce returns ridentity. Otherwise, it returns (fold proc (car list) (cdr list)). In other words, we compute (fold proc ridentity list).
Note: ridentity is used only in the empty-list case. You typically use reduce when applying proc is expensive and you’d like to avoid the extra application incurred when fold applies proc to the head of list and the identity value, redundantly producing the same value passed in to proc. For example, if proc involves searching a file directory or performing a database query, this can be significant. In general, however, fold is useful in many contexts where reduce is not (consider the examples given in the fold definition — only one of the five folds uses a function with a right identity. The other four may not be performed with reduce).
;; Take the max of a list of non-negative integers.
(reduce max 0 nums)reduce-right is the fold-right variant of reduce. It obeys the following definition:
Three (notional) rows here. [wcm](reduce-right proc ridentity '()) = ridentity
(reduce-right proc ridentity '(e1)) = (proc e1 ridentity) = e1
(reduce-right proc ridentity '(e1e2 …)) = (fold-right proc e1 '(e2 …))
In other words, we compute (fold-right proc ridentity list), but as with reduce, only use ridentity in the empty-list case.
;; Append a bunch of lists together.
(reduce-right append '() list-of-lists)unfold is best described by its basic recursion:
(unfold p f g seed) = (if (p seed)
(tail-gen seed)
(cons (f seed)
(unfold p f g (g seed)))Determines when to stop unfolding.
Maps each seed value to the corresponding list element.
Maps each seed value to next seed value.
The “state” value for the unfold.
Creates the tail of the list; defaults to (lambda (x) '()).
In other words, we use g to generate a sequence of seed values
Is <mml:mo> the right markup for '…'? [wcm]These seed values are mapped to list elements by f, producing the elements of the result list in a left-to-right order. P says when to stop.
;; List of squares: 1² … 10²
(unfold (lambda (x) (> x 10))
(lambda (x) (* x x))
(lambda (x) (+ x 1))
1)
(unfold null-list? car cdr lis) ; Copy a proper list.
;; Read current input port into a list of values.
(unfold eof-object? values (lambda (x) (read)) (read))
;; Copy a possibly non-proper list:
(unfold not-pair? car cdr lis
values)
;; Append head onto tail:
(unfold null-list? car cdr head
(lambda (x) tail))unfold-right constructs a list with the following loop:
(let lp ((seed seed) (lis tail))
(if (p seed)
lis
(lp (g seed)
(cons (f seed) lis))))Determines when to stop unfolding.
Maps each seed value to the corresponding list element.
Maps each seed value to next seed value.
The “state” value for the unfold.
list terminator; defaults to '().
In other words, we use g to generate a sequence of seed values
Is <mml:mo> the right markup for '…'? [wcm]These seed values are mapped to list elements by f, producing the elements of the result list in a right-to-left order. P says when to stop.
;; List of squares: 1² ... 10²
(unfold-right zero?
(lambda (x) (* x x))
(lambda (x) (- x 1))
10)
;; Reverse a proper list.
(unfold-right null-list? car cdr lis)
;; Read current input port into a list of values.
(unfold-right eof-object? values (lambda (x) (read)) (read))
;; (append-reverse rev-head tail)
(unfold-right null-list? car cdr rev-head tail)Map proc over the elements of the lists, just as in the map function. However, the results of the applications are appended together (as with append) to make the final result. The dynamic order in which the various applications of proc are made is not specified. At least one of the clist arguments must be finite.
(append-map (lambda (x) (list x (- x))) '(1 3 8))⇒(1 -1 3 -3 8 -8)
Map proc over the elements of the lists, just as in the map function. However, the results of the applications are appended together (as with append!) to make the final result. The dynamic order in which the various applications of proc are made is not specified. At least one of the clist arguments must be finite.
(append-map! (lambda (x) (list x (- x))) '(1 3 8))⇒(1 -1 3 -3 8 -8)
Linear-update variant of map — map! is allowed, but not required, to alter the cons cells of list1 to construct the result list. The dynamic order in which the various applications of proc are made is not specified.
In the -ary case, clist2, clist3, … must have at least as many elements as list1.
A variant of the map procedure that guarantees to apply proc across the elements of the clist arguments in a left-to-right order. This is useful for mapping procedures that both have side effects and return useful values. At least one of the clist arguments must be finite.
Like for-each, but proc is applied to successive sublists of the argument lists. That is, proc is applied to the cons cells of the lists, rather than the lists’ elements. These applications occur in left-to-right order. At least one of the clist arguments must be finite.
Proc may reliably apply set-cdr! to the pairs it is given without altering the sequence of execution.
(pair-for-each (lambda (pair)
(display pair)
(newline))
'(a b c))
(a b c)
(b c)
(c)
Like map, but only true values are saved. The dynamic order in which the various applications of proc are made is not specified. At least one of the clist arguments must be finite.
(filter-map (lambda (x) (and (number? x) (* x x))) '(a 1 b 3 c 7))⇒(1 9 49)
Return all the elements of list that satisfy predicate pred. Elements that appear in the result list occur in the same order as they occur in list. The returned list may share a common tail with list. The dynamic order in which the various applications of pred are made is not specified.
(filter even? '(0 7 8 8 43 -4))⇒(0 8 8 -4)
Linear-update variant of filter. filter! is allowed, but not required, to alter the cons cells in list to construct the result list.
Partitions the elements of list with predicate pred, and returns two values: the list of in-elements and the list of out-elements. Elements occur in the result lists in the same order as they occur in list. The dynamic order in which the various applications of pred are made is not specified. One of the returned lists may share a common tail with list.
(partition symbol? '(one 2 3 four five 6))⇒(one four five) (2 3 6)
Linear-update variant of partition. partition! is allowed, but not required, to alter the cons cells in list to construct the result lists.
Returns list without the elements that satisfy predicate pred. Elements that appear in the result list occur in the same order as they occur in list. The returned list may share a common tail with list. The dynamic order in which the various applications of pred are made is not specified.
(remove even? '(0 7 8 8 43 -4))⇒(7 43)
The following procedures all search lists for a leftmost element satisfying some criteria. This means they do not always examine the entire list; thus, there is no efficient way for them to reliably detect and signal an error when passed a dotted or circular list. Here are the general rules describing how these procedures work when applied to different kinds of lists:
The SRFI uses a definition list here. DocBook's <variablelist> doesn't seem quite right. I considered using <formalparagraph>, but there are indications in the schema that PHM wants to avoid those. Hence sections, for now. [wcm].The standard, canonical behavior happens in this case.
It is an error to pass these procedures an improper list.
It is an error to pass these procedures a circular list that does not contain an element satisfying the search criteria. Note that the procedure is not required to detect this case; it may simply diverge. It is, however, acceptable to search a circular list if the search is successful — that is, if the list contains an element satisfying the search criteria.
Here are some examples, using the find and any procedures as canonical representatives:
;; Proper list — success (find even? '(1 2 3))⇒2
(any even? '(1 2 3))⇒#t
;; Proper list — failure (find even? '(1 7 3))⇒#f
(any even? '(1 7 3))⇒#f
;; Circular list — success (find even? (circular-list 1 6 3))⇒6
(any even? (circular-list 1 6 3))⇒#t
Return the first element of clist that satisfies predicate pred; false if no element does.
Note: Note that find has an ambiguity in its lookup semantics — if find 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 list being searched is known not to contain any #f elements, or the list is guaranteed to have an element satisfying pred. However, in cases where this ambiguity can arise, you should use find-tail instead of find — find-tail has no such ambiguity:
(cond ((find-tail pred lis) =>
(lambda (pair) …)) ; Handle (car pair)
(else …)) ; Search failed.(find even? '(3 1 4 1 5 9))⇒4
Return the first pair of clist whose car satisfies pred. If no pair does, return false.
In the circular-list case, this procedure “rotates” the list.
Note: Find-tail is essentially drop-while, where the sense of the predicate is inverted: Find-tail searches until it finds an element satisfying the predicate; drop-while searches until it finds an element that doesn’t satisfy the predicate.
(find-tail even? '(3 1 37 -8 -5 0 0))⇒(-8 -5 0 0)
(find-tail even? '(3 1 37 -5))⇒#f
;; member x lis:
(find-tail (lambda (elt) (equal? x elt)) lis)Returns the longest initial prefix of clist whose elements all satisfy the predicate pred.
(take-while even? '(2 18 3 10 22 9))⇒(2 18)
Linear-update variant of take-while. It is allowed, but not required, to alter the argument clist to produce the result.
Drops the longest initial prefix of clist whose elements all satisfy the predicate pred, and returns the rest of the list.
The circular-list case may be viewed as “rotating” the list.
(drop-while even? '(2 18 3 10 22 9))⇒(3 10 22 9)
Splits clist into the longest initial prefix whose elements all satisfy pred, and the remaining tail.
span is equivalent to
(values (take-while pred clist)
(drop-while pred clist))(span even? '(2 18 3 10 22 9))⇒(2 18) (3 10 22 9)
Linear-update variant of span. span! is allowed, but not required, to alter the argument list to produce the results.
break is like span, but it inverts the sense of pred: the tail commences with the first element of the input clist that satisfies the predicate.
(break even? '(3 1 4 1 5 9))⇒(3 1) (4 1 5 9)
Linear-update variant of break. break! is allowed, but not required, to alter the argument list to produce the results.
Applies pred across the lists, returning true if the predicate returns true on any application.
If there are list arguments clist1 … clistn, then pred must be a procedure taking arguments and returning a single value.
any applies pred to the first elements of the clisti parameters. If this application returns a true value, any immediately returns that value. Otherwise, it iterates, applying pred to the second elements of the clisti parameters, then the third, and so forth. The iteration stops when a true value is produced or one of the lists runs out of values; in the latter case, any returns #f. The application of pred to the last element of the lists is a tail call.
Note: Note the difference between find and any — find returns the element that satisfied the predicate; any returns the true value that the predicate produced.
This rationale is contradicted by other procedures in the library (e.g. lset=) which always returns booleans. [wcm]
Like every, any’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.
(any integer? '(a 3 b 2.7))⇒#t
(any integer? '(a 3.1 b 2.7))⇒#f
(any < '(3 1 4 1 5) '(2 7 1 8 2))⇒#t
Applies pred across the lists, returning true if the predicate returns true on every application.
If there are list arguments clist1 … clistn, then pred must be a procedure taking arguments and returning a single value.
every applies pred to the first elements of the clisti parameters. If this application returns false, every immediately returns false. Otherwise, it iterates, applying pred to the second elements of the clisti parameters, then the third, and so forth. The iteration stops when a false value is produced or one of the lists runs out of values. In the latter case, every returns the true value produced by its final application of pred. The application of pred to the last element of the lists is a tail call.
If one of the clisti has no elements, every simply returns #t.
Note: Like any, every’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.
Return the index of the leftmost element that satisfies pred.
If there are list arguments clist1 … clistn, then pred must be a function taking arguments and returning a single value.
list-index applies pred to the first elements of the clisti parameters. If this application returns true, list-index immediately returns zero. Otherwise, it iterates, applying pred to the second elements of the clisti parameters, then the third, and so forth. When it finds a tuple of list elements that cause pred to return true, it stops and returns the zero-based index of that position in the lists.
The iteration stops when one of the lists runs out of values; in this case, list-index returns #f.
(list-index even? '(3 1 4 1 5 9))⇒2
(list-index < '(3 1 4 1 5 9 2 5 6) '(2 7 1 8 2))⇒1
(list-index = '(3 1 4 1 5 9 2 5 6) '(2 7 1 8 2))⇒#f
delete uses the comparison procedure proc, which defaults to equal?, to find all elements of list that are equal to obj, and deletes them from list. The dynamic order in which the various applications of = are made is not specified.
The list is not disordered — elements that appear in the result list occur in the same order as they occur in the argument list. The result may share a common tail with the argument list.
The comparison procedure is used in this way:
(proc obj ei).That is, obj is always the first argument, and a list element is always the second argument. The comparison procedure will be used to compare each element of list exactly once; the order in which it is applied to the various ei is not specified.
Note: Fully general element deletion can be performed with the remove and remove! procedures, e.g.:
;; Delete all the even elements from lis:
(remove even? lis)(delete 5 '(3 5 1 7) <)⇒(3 5 1)
delete! is the linear-update variant of delete. It is allowed, but not required, to alter the cons cells in its argument list to construct the result.
delete-duplicatesremoves duplicate elements from the list argument. If there are multiple equal elements in the argument list, the result list 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 list — delete-duplicates does not disorder the list.
The proc parameter is used to compare the elements of the list; it defaults to equal?. If comes before in list, then the comparison is performed (procx y). The comparison procedure will be used to compare each pair of elements in list no more than once; the order in which it is applied to the various pairs is not specified.
Implementations of delete-duplicates are allowed to share common tails between argument and result lists — for example, if the list argument contains only unique elements, it may simply return exactly this list.
Note: Be aware that, in general, delete-duplicates runs in time for -element lists.
(delete-duplicates '(a b a c a b c z))⇒(a b c z)
;; Clean up an association list: (delete-duplicates '((a . 3) (b . 7) (a . 9) (c . 1)) (lambda (x y) (eq? (car x) (car y))))⇒((a . 3) (b . 7) (c . 1))
delete-duplicates! is the linear-update variant of delete-duplicates; it is allowed, but not required, to alter the cons cells in its argument list to construct the result.
An association list (or alist) is a list of pairs. The car of each pair contains a key value, and the cdr contains the associated data value. They can be used to construct simple look-up tables in Scheme. Note that association lists are probably inappropriate for performance-critical use on large data; in these cases, hash tables or some other alternative should be employed.
Cons a new alist entry mapping key to value onto alist.
Make a fresh copy of alist. This means copying each pair that forms an association as well as the spine of the list, i.e.
(lambda (a)
(map (lambda (elt) (cons (car elt) (cdr elt)))
a))Deletes all associations from alist with the given key, using key-comparison procedure equals, which defaults to equal?. The dynamic order in which the various applications of equals are made is not specified.
Return values may share common tails with the alist argument. The alist is not disordered — elements that appear in the result alist occur in the same order as they occur in the argument alist.
The comparison procedure is used to compare the element keys ki of alist’s entries to the key parameter in this way:
(equals key ki).
Thus, one can reliably remove all entries of alist whose keys are greater than five with (alist-delete 5 alist >).
alist-delete! is the linear-update variant of alist-delete. It is allowed, but not required, to alter cons cells from the alist parameter to construct the result.
These procedures implement operations on sets represented as lists of elements. They all take an equals argument used to compare elements of lists. This equality procedure is required to be consistent with eq?. That is, it must be the case that
(eq? x y) ⇒ (equals x y).Note that this implies, in turn, that two lists that are eq? are also set-equal by any legal comparison procedure. This allows for constant-time determination of set operations on eq? lists.
Note: Be aware that these procedures typically run in time for - and -element list arguments. Performance-critical applications operating upon large sets will probably wish to use other data structures and algorithms.
Returns true iff every listi is a subset of listi+1, using equals for the element-equality procedure. List is a subset of list if every element in is equal to some element of . When performing an element comparison, the equals procedure’s first argument is an element of ; its second, an element of .
It would be better to define these trivial cases explicitly. [wcm](lset<= eq? '(a) '(a b a) '(a b c c))⇒#t
;; Trivial cases: (lset<= eq?)⇒#t
(lset<= eq? '(a))⇒#t
Returns true iff every listi is set-equal to listi+1, using equals for the element-equality procedure. “Set-equal” simply means that listi is a subset of listi+1, and listi+1 is a subset of listi. The equals procedure’s first argument is an element of listi; its second is an element of listi+1.
It would be better to define these trivial cases explicitly. [wcm](lset= eq? '(b e a) '(a e b) '(e e b a))⇒#t
;; Trivial cases: (lset= eq?)⇒#t
(lset= eq? '(a))⇒#t
Adds the elti elements not already in the list parameter to the result list. The result shares a common tail with the list parameter. The new elements are added to the front of the list, but no guarantees are made about their order. The equals parameter is an equality procedure used to determine if an elti is already a member of list. Its first argument is an element of list; its second is one of the elti.
The list parameter is always a suffix of the result — even if the list parameter contains repeated elements, these are not reduced.
(lset-adjoin eq? '(a b c d c e) 'a 'e 'i 'o 'u)⇒(u o i a b c d c e)
Note that the order of the first three elements of the result list is unspecified.
Returns the union of the lists, using equals for the element-equality procedure.
The union of lists and is constructed as follows:
If is the empty list, the result is (or a copy of ).
Otherwise, the result is initialised to be list (or a copy of ).
Proceed through the elements of list in a left-to-right order. If is such an element of , compare every element of the current result list to : (equals r b). If all comparisons fail, is consed onto the front of the result.
However, there is no guarantee that equals will be applied to every pair of arguments from and . In particular, if is eq? to , the operation may immediately terminate.
In the -ary case, the two-argument list-union operation is simply folded across the argument lists.
(lset-union eq? '(a b c d e) '(a e i o u))⇒(u o i a b c d e)
It would be better to define these trivial cases a little more explicitly. The paragraph immediately before the examples defines them, gnomically. [wcm];; Repeated elements in list1 are preserved: (lset-union eq? '(a a c) '(x a x))⇒(x a a c)
;; Trivial cases: (lset-union eq?)⇒()
(lset-union eq? '(a b c))⇒(a b c)
Linear-update variant of lset-union which is allowed, but not required, to alter the cons cells from any of its list parameters to construct its result.
Returns the intersection of the lists, using equals for the element-equality procedure.
The intersection of lists and comprises every element of that is equal in the sense of equals to some element of : (equals a b), for in , and in . Note this implies that an element which appears in and multiple times in list will also appear multiple times in the result.
The order in which elements appear in the result is the same as the order in which they appear in list1 — that is, lset-intersection essentially filters list1, without disarranging element order. The result may share a common tail with list1.
In the -ary case, the two-argument list-intersection operation is simply folded across the argument lists. However, the dynamic order in which the applications of equals are made is not specified. The procedure may check an element of list1 for membership in every other list before proceeding to consider the next element of list1, or it may completely intersect list1 and list2 before proceeding to list3, or it may go about its work in some third order.
(lset-intersection eq? '(a b c d e) '(a e i o u))⇒(a e)
;; Repeated elements in list1 are preserved: (lset-intersection eq? '(a x y a) '(x a x z))⇒'(a x a)
;; Trivial case: (lset-intersection eq? '(a b c))⇒(a b c)
Linear-update variant of lset-intersection which is allowed, but not required, to alter the cons cells in its first list parameter to construct its result.
Returns the difference of the lists, using equals for the element-equality procedure — all the elements of list1 that are not equals to any element from one of the other listi parameters.
The equals procedure’s first argument is always an element of list1; its second is an element of one of the other listi. Elements that are repeated multiple times in the list1 parameter will occur multiple times in the result.
The order in which elements appear in the result is the same as they appear in list1 — that is, lset-difference essentially filters list1, without disarranging element order. The result may share a common tail with list1.
The dynamic order in which the applications of equals are made is not specified. The procedure may check an element of list1 for membership in every other list before proceeding to consider the next element of list1, or it may completely compute the difference of list1 and list2 before proceeding to list3, or it may go about its work in some third order.
(lset-difference eq? '(a b c d e) '(a e i o u))⇒(b c d)
;; Trivial case: (lset-difference eq? '(a b c))⇒(a b c)
Linear-update variant of lset-difference which is allowed, but not required, to alter the cons cells in its first list parameter to construct its result.
Returns the exclusive-or of the sets, using equals for the element-equality procedure. If there are exactly two lists, this is all the elements that appear in exactly one of the two lists. The operation is associative, and thus extends to the -ary case — the elements that appear in an odd number of the lists. The result may share a common tail with any of the listi parameters.
More precisely, for two lists and , is a list of
every element of such that there is no element of such that (equals a b), and
every element of such that there is no element of such that (equals b a).
However, an implementation is allowed to assume that equals is symmetric — that is, that
(equals ) ⇒ (equals ).
This means, for example, that if a comparison (equals a b) produces true for some in and in , both and may be removed from inclusion in the result.
In the -ary case, the binary-xor operation is simply folded across the lists.
It would be better to define these trivial cases a little more explicitly. The paragraph immediately before the examples defines them, gnomically. [wcm](lset-xor eq? '(a b c d e) '(a e i o u))⇒(d c b i o u)
;; Trivial cases: (lset-xor eq?)⇒()
(lset-xor eq? '(a b c d e))⇒(a b c d e)
Linear-update variant of lset-xor which is allowed, but not required, to alter the cons cells in its first list parameter to construct its result.
Returns two values — the difference and the intersection of the lists. Is equivalent to
(values (lset-difference equals list1 list2 …)
(lset-intersection equals list1 (lset-union equals list2 …)))but can be implemented more efficiently.
The equals procedure’s first argument is an element of list1; its second is an element of one of the other listi.
Either of the answer lists may share a common tail with list1. This operation essentially partitions list1.
Linear-update variant of lset-diff+intersection which is allowed, but not required, to alter the cons cells in its first list parameter to construct its result.
© 1998–1999 Olin Shivers.
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.
A box is a container for an object of any Scheme type, including another box. It is like a single-element vector, or half of a pair, or a direct representation of state. Boxes are normally used as minimal mutable storage, and can inject a controlled amount of mutability into an otherwise immutable data structure (or one that is conventionally treated as immutable).
The behavior of boxes with the equivalence predicates eq?, eqv?, and equal? is the same as if they were implemented with records. That is, two boxes are both eq? and eqv? iff they are the product of the same call to box and not otherwise, and while they must be equal? if they are eqv?, the converse is implementation-dependent.
© John Cowan 2013. 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.