Chapter 12

The Built-In Functions

Collection Operations

The generic functions described in this section have predefined methods for the built-in collection classes (and sequence classes, where appropriate). The details of these predefined methods have not yet been specified.

Note to implementors: Functions such as map, map-as that return a new collection cannot rely on the type they instantiate having a valid default for fill:. Therefore, when the size of the result is nonzero, these functions should compute the first element of the result before making the collection and specify that element as the fill: value. Otherwise a spurious type error could occur when making the collection.

Collection Properties

empty? [Open Generic Function]


Returns true if its argument is empty.

Signature:

empty? object boolean

Arguments:
object

An instance of <object>.

Values:
boolean

An instance of <boolean>.

Description:

Returns true if object is empty. Otherwise returns #f.

empty? collectionboolean [G.F. Method]

A set of methods defined for the class <collection> returns true if the collection has zero elements.

size [Open Generic Function]


Returns the size of its argument.

Signature:

size object #rest objects

Arguments:
object

An instance of <object>.

Values:
objects

Instances of <object>.

Description:

Returns the size of object.

size collectioninteger-or-false [G.F. Method]

When called on a collection, size returns the numbers of keys in the collection. This default method simply counts while iterating through the collection. size may return #f for collections of unbounded size.

size arraysize [G.F. Method]

The method for <array> is equivalent to

reduce(\*, 1, dimensions (array))
size listinteger-or-false [Sealed G.F. Method]

For circular lists, size is guaranteed to terminate and return #f. For noncircular lists, size returns an integer size value.

size rangesize [Sealed G.F. Method]

For unbounded ranges, size always terminates and returns #f. For finite ranges, size returns an integer.

size tablesize [Sealed G.F. Method]

The class <table> provides an implementation of size for use by its subclasses. The method returns an instance of <integer>.

size-setter [Open Generic Function]


Sets the size of an object.

Signature:

size-setter new-size object new-size

Arguments:
new-size

An instance of <object>.

object

An instance of <object>.

Values:
new-size

An instance of <object>.

Description:

Sets the size of object to new-size.

object is modified by this operation.

Methods are provided for stretchy sequences; that is, for collections that are instances both of <stretchy-collection> and of <sequence>.

size-setter sets the size of a stretchy sequence to be new-size. The stretchy sequence is modified by this operation. If new-size is less than or equal to the original size of the stretchy sequence, then the first new-size elements of the stretchy sequence are retained at the same positions. If new-size is greater than the original size of the stretchy sequence, then the previous elements of the stretchy sequence are retained at the same positions, and enough new elements are added to reach the new size. The value of each new element is the same as would have been used if the stretchy sequence had been created with make, specifying size: new-size but not fill:.

It is not specified how size-setter adds new elements to the stretchy sequence. In particular, it is not required to call add! or any other predefined function.

rank [Open Generic Function]


Returns the number of dimensions of an array.

Signature:

rank array rank

Arguments:
array

An instance of <array>.

Values:
rank

An instance of <integer>.

Description:

Returns the number of dimensions (the rank) of array.

rank arrayrank [G.F. Method]

The method for <array> computes rank by calling size on the dimensions of array.

row-major-index [Open Generic Function]


Returns the row-major-index position of an array element.

Signature:

row-major-index array #rest subscripts index

Arguments:
array

An instance of <array>.

subscripts

Instances of <integer>.

Values:
index

An instance of <integer>.

Description:

Computes the position according to the row-major ordering of array for the element that is specified by subscripts, and returns the position of that element.

An error is signaled if the number of subscripts is not equal to the rank of the array. An error is signaled if any of the subscripts are out of bounds for array.

row-major-index array #rest subscriptsindex [G.F. Method]

The method for <array> computes the index using the subscripts and the result of calling dimensions on the array.

dimensions [Open Generic Function]


Returns the dimensions of an array.

Signature:

dimensions array sequence

Arguments:
array

An instance of <array>.

Values:
sequence

An instance of <sequence>. The elements of this sequences will be instances of <integer>.

Description:

Returns the dimensions of array, as a sequence of integers. The consequences are undefined if the resulting sequence is modified. This function forms the basis for all the other array operations. Each concrete subclass of <array> must either provide or inherit an implementation of this function.

dimensions vectorsequence [G.F. Method]

Returns a sequence whose single element is the size of the vector.

dimension [Open Generic Function]


Returns the size of a specified dimension of an array.

Signature:

dimension array axis dimension

Arguments:
array

An instance of <array>.

axis

An instance of <integer>.

Values:
dimension

An instance of <integer>.

Description:

Returns the axis dimension of array.

axis must be a non-negative integer less than the rank of array. An error is signaled if axis is out of bounds for array.

dimension array axisdimension [G.F. Method]

The method for <array> calls element on the result of calling dimensions on the array, using the axis number as the key.

key-test [Open Generic Function]


Returns the function used by its collection argument to compare keys.

Signature:

key-test collection test-function

Arguments:
collection

An instance of <collection>.

Values:
test-function

An instance of <function>. The function used by the collection to compare keys.

Description:

Returns the function used by collection to compare keys.

All collection classes must provide or inherit a method that returns a result consistent with their iteration protocol and element methods. A given method for key-test must return the same value (compared with ==) each time it is called.

key-test sequencetest-function [Sealed G.F. Method]

The method of key-test for sequences returns the function ==.

key-test tabletest-function [Sealed G.F. Method]

The method of key-test for instances of <table> returns the first value of table-protocol(table).

key-sequence [Open Generic Function]


Returns a sequence containing the keys of its collection argument.

Signature:

key-sequence collection keys

Arguments:
collection

An instance of <collection>.

Values:
keys

An instance of <sequence> containing the keys of collection.

Description:

Returns a sequence containing the keys of collection.

Although elements may be duplicated in a collection, keys, by their nature, must be unique; two different elements in a collection may not share a common key, even though distinct keys may yield identical elements.

The order in which the keys from collection appear in the key sequence is unspecified if collection is unstable under iteration. In particular, different calls to key-sequence with the same argument may yield differently ordered key sequences. If collection is stable under iteration, however, the resulting sequence of keys will be in the natural order for collection.

Selecting Elements

element [Open Generic Function]


Returns the collection element associated with a particular key.

Signature:

element collection key #key default element

Arguments:
collection

An instance of <collection>.

key

An instance of <object>.

default

An instance of <object>.

Values:
element

An instance of <object>.

Description:

Returns the element associated with key in collection. If no element is associated with key, then the behavior of element depends on whether it was called with a default argument: if a default argument was passed, its value is returned; otherwise, an error is signaled.

All collections are required to implement element.

element simple-vector index #key defaultelement [Sealed G.F. Method]

There is a constant time implementation of element for all general instances of <simple-vector>.

element unicode-string index #key defaultcharacter [Sealed G.F. Method]

The class <unicode-string> provides a constant time implementation for the element function.

element byte-string index #key defaultcharacter [Sealed G.F. Method]

The class <byte-string> provides a constant time implementation for the element function.

element table key #key defaultelement [Sealed G.F. Method]

The class <table> provides a default implementation for the element function.

element-setter [Open Generic Function]


Sets the collection element associated with a particular key.

Signature:

element-setter new-value mutable-collection key new-value

Arguments:
new-value

An instance of <object>.

mutable-collection

An instance of <mutable-collection>.

key

An instance of <object>.

Values:
new-value

Zero or more instances of <object>.

Description:

Alters mutable-collection so that the value associated with key will subsequently be new-value. If mutable-collection is stretchy, element-setter may also change its size (for example, by adding new keys with values).

An error is signaled if a program calls element-setter with a key that is not already a key to collection, unless the collection is stretchy.

Stretchy collections allow element-setter to be called with a key that is not present in the collection, expanding the collection as necessary to add a new element in that case. Each concrete subclass of <stretchy-collection> must provide or inherit a method for element-setter that behaves as follows when there is not already an element present for the indicated key:

  • If the class is a subclass of <explicit-key-collection>, adds a new element to the collection with the indicated key.
  • If the class is a subclass of <sequence>, first calls size-setter on the key + 1 and the collection to expand the sequence. The key must be a non-negative integer.
element-setter new-element simple-vector index
new-element
[Sealed G.F. Method]

There is a constant time implementation of element-setter for all general instances of <simple-vector>.

element-setter new-value table key [Sealed G.F. Method]

The class <table> provides an implementation of element-setter for use by its subclasses. If no element with the given key exists, element-setter will add the key and new-value to the table.

element-setter character unicode-string index [Sealed G.F. Method]
character

The class <unicode-string> provides a constant time implementation for the element-setter function.

element-setter character byte-string indexcharacter [Sealed G.F. Method]

The class <byte-string> provides a constant time implementation for the element-setter function.

aref [Open Generic Function]


Returns the array element indicated by a set of indices.

Signature:

aref array #rest indices element

Arguments:
array

An instance of <array>.

indices

Instances of <integer>.

Values:
element

An instance of <object>.

Description:

Returns the element of array indicated by indices.

An error is signaled if the number of indices is not equal to the rank of the array. An error is signaled if any of the indices are out of bounds for the array.

aref array #rest indiceselement [G.F. Method]

The method for <array> calls element on the array, using as the key the result of applying row-major-index to the array and indices.

aref-setter [Open Generic Function]


Sets the array element indicated by a set of indices.

Signature:

aref-setter new-value array #rest indices new-value

Arguments:
new-value

An instance of <object>.

array

An instance of <array>.

indices

Instances of <integer>.

Values:
new-value

An instance of <object>.

Description:

Sets the element of array indicated by indices to the new-value and returns the new-value.

array is modified by this operation.

An error is signaled if the number of indices is not equal to the rank of the array. An error is signaled if any of the indices are out of bounds for array. An error is signaled if the array is limited to hold objects of a particular type and the new value is not an instance of that type.

aref-setter new-value array #rest indicesnew-value [G.F. Method]

The method for <array> calls element-setter on the array and new value, using as the key the result of applying row-major-index to the array and indices.

first [Function]


Returns the first element of a sequence.

Signature:

first sequence #key default value

Arguments:
sequence

An instance of <sequence>.

default

An instance of <object>.

Values:
value

An instance of <object> .

Description:

Returns the first element of the sequence by calling element with the supplied arguments and the corresponding index.

Note that because element is zero-based, first(seq) is equivalent to element(seq, 0) and seq[0].

second [Function]


Returns the second element of a sequence.

Signature:

second sequence #key default value

Arguments:
sequence

An instance of <sequence>.

default

An instance of <object>.

Values:
value

An instance of <object>.

Description:

Returns the second element of the sequence by calling element with the supplied arguments and the corresponding index.

third [Function]


Returns the third element of a sequence.

Signature:

third sequence #key default value

Arguments:
sequence

An instance of <sequence>.

default

An instance of <object>.

Values:
value

An instance of <object>.

Description:

Returns the third element of the sequence by calling element with the supplied arguments and the corresponding index.

first-setter [Function]


Sets the first element of a mutable sequence.

Signature:

first-setter new-value mutable-sequence new-value

Arguments:
new-value

An instance of <object>.

mutable-sequence

An instance of <mutable-sequence>.

Values:
new-value

An instance of <object>.

Description:

Sets the first element of the mutable-sequence and returns the new-value, by calling element-setter with the supplied arguments and the corresponding index.

Note that because element-setter is zero-based, first-setter(val, seq) is equivalent to element-setter(val, seq, 0) and seq[0] := val.

second-setter [Function]


Sets the second element of a mutable sequence.

Signature:

second-setter new-value mutable-sequence new-value

Arguments:
new-value

An instance of <object>.

mutable-sequence

An instance of <mutable-sequence>.

Values:
new-value

An instance of <object>.

Description:

Sets the second element of the mutable-sequence and returns the new-value, by calling element-setter with the supplied arguments and the corresponding index.

third-setter [Function]


Sets the third element of a mutable sequence.

Signature:

third-setter new-value mutable-sequence new-value

Arguments:
new-value

An instance of <object>.

mutable-sequence

An instance of <mutable-sequence>.

Values:
new-value

An instance of <object>.

Description:

Sets the third element of the mutable-sequence and returns the new-value, by calling element-setter with the supplied arguments and the corresponding index.

last [Open Generic Function]


Returns the last element of a sequence.

Signature:

last sequence #key default value

Arguments:
sequence

An instance of <sequence>.

default

An instance of <object>.

Values:
value

Zero or more instances of <object>.

Description:

Returns the last element of sequence.

If the sequence is empty, then the behavior of last depends on whether it was called with a default argument. If the default argument was supplied, its value is returned; otherwise, an error is signaled.

last (#("emperor", "of", "china"))
  "china"

last-setter [Open Generic Function]


Sets the last element of a mutable sequence.

Signature:

last-setter new-value mutable-sequence new-value

Arguments:
new-value

An instance of <object>.

mutable-sequence

An instance of <mutable-sequence>.

Values:
new-value

An instance of <object>.

Description:

Replaces the last element of mutable-sequence with new-value.

mutable-sequence is modified by this operation.

new-value must obey any type restrictions for elements of mutable-sequence . An error is signaled if mutable-sequence is empty or unbounded.

define variable my-list = list (1, 2, 3)
my-list
  #(1, 2, 3)
last (my-list) := 4
  4
my-list
  #(1, 2, 4)
define variable my-empty-vector = vector()
my-empty-vector
  #[]
last (my-empty-vector) := 4
{error}

Returns the head of a list.

Signature:

head list object

Arguments:
list

An instance of <list>.

Values:
object

An instance of <object>.

Description:

Returns the head of list.

If list is a pair, head returns the value of the head slot. If list is the empty list, head returns the empty list.

head (#(4, 5, 6))
  4
head (#())
  #()

tail [Function]


Returns the tail of a list.

Signature:

tail list object

Arguments:
list

An instance of <list>.

Values:
object

An instance of <object>.

Description:

Returns the tail of list.

If list is a pair, tail returns the value of the tail slot. If list is the empty list, tail returns the empty list.

tail (#(4, 5, 6))
 ⇒ #(5, 6)
tail (#())
 ⇒ #()

head-setter [Function]


Sets the head of a pair.

Signature:

head-setter object pair object

Arguments:
object

An instance of <object>.

pair

An instance of <pair>.

Values:
object

An instance of <object>.

Description:

Sets the head of pair to contain object and returns object.

pair is modified by this operation.

define variable x = list (4, 5, 6)
head (x) := 9
 ⇒ 9
x
 ⇒ #(9, 5, 6)

tail-setter [Function]


Sets the tail of a pair.

Signature:

tail-setter object pair object

Arguments:
object

An instance of <object>.

pair

An instance of <pair>.

Values:
object

An instance of <object>.

Description:

Sets the tail of pair to contain object and returns object.

pair is modified by this operation.

define variable x = list (4, 5, 6)
tail (x) := #(9, 8, 7)
  #(9, 8, 7)
x
  #(4, 9, 8, 7)
tail (x) := "dot"
  "dot"
x
  #(4 . "dot")

Errata: In the published book, the final value of x is incorrect: #(4, 9, 8 . "dot")

Adding and Removing Elements

add [Open Generic Function]


Adds an element to a sequence.

Signature:

add source-sequence new-element result-sequence

Arguments:
source-sequence

An instance of <sequence>.

new-element

An instance of <object>.

Values:
result-sequence

An instance of <sequence>.

Description:

Returns a sequence that contains new-element and all the elements of source-sequence. The result-sequence may or may not be freshly allocated. It may share structure with a preexisting sequence.

source-sequence is not modified by this operation.

The result-sequence's size is one greater than the size of source-sequence. The generic function add doesn't specify where the new element will be added, although individual methods may do so.

define variable *numbers* = #(3, 4, 5)
add (*numbers*, 1)
  ⇒  #(1, 3, 4, 5) 
*numbers*
  ⇒  #(3, 4, 5)

add! [Open Generic Function]


Adds an element to a sequence.

Signature:

add! source-sequence new-element result-sequence

Arguments:
source-sequence

An instance of <sequence>.

new-element

An instance of <object>.

Values:
result-sequence

An instance of <sequence>.

Description:

Returns a sequence that contains new-element and all the elements of source-sequence. The result-sequence may or may not be freshly allocated. It may share structure with a preexisting sequence. source-sequence and result-sequence may or may not be ==.

source-sequence may be modified by this operation.

result-sequence's size is one greater than the size of source-sequence. The generic function add! doesn't specify where the new element will be added, although individual methods may do so.

define variable *numbers* = list (3, 4, 5)
add! (*numbers*, 1)
  ⇒  #(1, 3, 4, 5)
*numbers*
  ⇒ {undefined}
add! deque new-value deque [Sealed G.F. Method]

The result of add! on a deque is == to the deque argument, which is modified by this operation. add! adds new-element at the beginning of the deque.

add! stretchy-vector new-element stretchy-vector [Sealed G.F. Method]

The result of add! on a stretchy vector is == to the stretchy-vector argument, which is modified by this operation. add! adds new-element at the end of the stretchy-vector.

add! list element pair [Sealed G.F. Method]

The result of add! on a list is equivalent to (pair element list). The result will share structure with the list argument, but it will not be == to the argument, and the argument will not be modified.

add-new [Open Generic Function]


Adds a new element to a sequence.

Signature:

add-new source-sequence new-element #key test result-sequence

Arguments:
source-sequence

An instance of <sequence>.

new-element

An instance of <object>.

test

An instance of <function>. The default is ==.

Values:
result-sequence

An instance of <sequence>.

Description:

Adds new-element to source-sequence if it is not already an element of source-sequence, as determined by the test function. If new-element is already a member of source-sequence, then source-sequence is returned unmodified.

If an element is added, add-new operates just as add would.

The test function may be noncommutative: it is always called with an element from source-sequence as its first argument and new-element as its second argument.

add-new (#(3, 4, 5), 1)
  ⇒  #(1, 3, 4, 5)
add-new (#(3, 4, 5), 4)
  ⇒  #(3, 4, 5)

add-new! [Open Generic Function]


Adds a new element to a sequence.

Signature:

add-new! source-sequence new-element #key test result-sequence

Arguments:
source-sequence

An instance of <sequence>.

new-element

An instance of <object>.

test

An instance of <function>. The default is ==.

Values:
result-sequence

An instance of <sequence>.

Description:

Adds new-element to source-sequence if it is not already an element of source-sequence, as determined by the test function. If new-element is already a member of source-sequence, then source-sequence is returned unmodified.

If an element is added, add-new! operates just as add! would.

The test function may be noncommutative: it is always called with an element from sequence as its first argument and new-element as its second argument.

add-new! (list (3, 4, 5), 1)
  ⇒  #(1, 3, 4, 5)
add-new! (list (3, 4, 5), 4)
  ⇒  #(3, 4, 5)

remove [Open Generic Function]


Removes an element from a sequence.

Signature:

remove source-sequence value #key test count result-sequence

Arguments:
source-sequence

An instance of <sequence>.

value

An instance of <object>.

test

An instance of <function>. The default is ==.

count

An instance of <integer> or #f. The default is #f.

Values:
result-sequence

An instance of <sequence>.

Description:

Returns a sequence consisting of the elements of source-sequence not equal to value. The result-sequence may or may not be freshly allocated. However, the source-sequence is never modified by remove.

test is a function that determines whether an element is equal to value. The test function may be noncommutative: it is always called with an element from source-sequence as its first argument and value as its second argument.

If count is #f, then all copies of value are removed. Otherwise, no more than count copies of value are removed (so additional elements equal to value might remain in result-sequence).

define variable *old-list* = list(1, 2, 3)
define variable *new-list* = remove(*old-list*, 1)
*new-list*
  ⇒  #(2, 3)
*new-list* == tail(*old-list*)
  ⇒  {undefined}

remove! [Open Generic Function]


Removes an element from a sequence.

Signature:

remove! source-sequence value #key test count result-sequence

Arguments:
source-sequence

An instance of <sequence>.

value

An instance of <object>.

test

An instance of <function>. The default is ==.

count

An instance of <integer> or #f. The default is #f.

Values:
result-sequence

An instance of <sequence>.

Description:

Returns a sequence consisting of the elements of source-sequence not equal to value. The result-sequence may or may not be freshly allocated, may or may not be == to the source-sequence, and may or may not share structure with the source-sequence. The source-sequence may be modified by remove!.

test is a function that determines whether an element is equal to value. The test function may be noncommutative: it is always called with an element from source-sequence as its first argument and value as its second argument.

If count is #f, then all copies of value are removed. Otherwise, no more than count copies of value are removed (so additional elements equal to value might remain in result-sequence).

remove! deque value #key test countdeque [Sealed G.F. Method]

The result of remove! on a deque is == to the deque argument. The argument is modified by this operation.

remove! stretchy-vector element #key test count [Sealed G.F. Method]
stretchy-vector

The result of remove! on a stretchy vector is == to the stretchy-vector argument. The argument is modified by this operation.

remove! list element #key test countlist [Sealed G.F. Method]

The result of remove! on a list may or may not be == to the list argument. The argument may be modified by this operation.

push [Open Generic Function]


Adds an element to the front of a deque.

Signature:

push deque new-value new-value

Arguments:
deque

An instance of <deque>.

new-value

An instance of <object>.

Values:
new-value

An instance of <object>. The same object that was passed in as an argument.

Description:

Augments deque by adding new-value to its front.

deque is modified by this operation.

pop [Open Generic Function]


Removes and returns the first element of a deque.

Signature:

pop deque first-element

Arguments:
deque

An instance of <deque>.

Values:
first-element

An instance of <object>.

Description:

Removes the first element from deque and returns it.

deque is modified by this operation.

push-last [Open Generic Function]


Adds an element to the end of a deque.

Signature:

push-last deque new-value new-value

Arguments:
deque

An instance of <deque>.

new-value

An instance of <object>.

Values:
new-value

An instance of <object>. The same object that was passed in as an argument.

Description:

Augments deque by adding new-value to its end.

deque is modified by this operation.

pop-last [Open Generic Function]


Removes and returns an element from the end of a deque.

Signature:

pop-last deque last-element

Arguments:
deque

An instance of <deque>.

Values:
last-element

An instance of <object>.

Description:

Removes the last element from deque and returns it.

deque is modified by this operation.

Reordering Elements

reverse [Open Generic Function]


Returns a sequence with elements in the reverse order of its argument sequence.

Signature:

reverse source-sequence result-sequence

Arguments:
source-sequence

An instance of <sequence>.

Values:
result-sequence

An instance of <sequence>.

Description:

Returns a sequence containing the same elements as source-sequence, but in reverse order. The result-sequence is generally of the same class as the source-sequence.

The result-sequence may or may not be freshly allocated. The source-sequence is not modified by this operation.

The consequences are undefined if the source-sequence is unbounded (circular or infinite).

define variable *x* = list("bim", "bam", "boom")
*x*
  ⇒  #("bim", "bam", "boom")
reverse(*x*)
  ⇒  #("boom", "bam", "bim")
*x*
  ⇒  #("bim", "bam", "boom")
reverse rangenew-range [Sealed G.F. Method]

Reversing a range produces another range. An unbounded range cannot be reversed.

reverse! [Open Generic Function]


Returns a sequence with elements in the reverse order of its argument sequence.

Signature:

reverse! source-sequence result-sequence

Arguments:
source-sequence

An instance of <sequence>.

Values:
result-sequence

An instance of <sequence>.

Description:

Returns a sequence containing the same elements as source-sequence, but in reverse order. The result-sequence is generally of the same class as the source-sequence.

The source-sequence may be modified by this operation. The result-sequence may or may not be freshly allocated. The source-sequence and the result-sequence may or may not be ==. Programs should never rely on this operation performing a side-effect on an existing sequence, but should instead use the value returned by the function.

The consequences are undefined if the source-sequence is unbounded (circular or infinite).

define variable *x* = list("bim", "bam", "boom")
*x*
  ⇒  #("bim", "bam", "boom")
reverse!(*x*)
  ⇒  #("boom", "bam", "bim")
*x*
  ⇒  {undefined}
reverse! rangerange [Sealed G.F. Method]

The result of reverse! on a range is == to the range argument. An unbounded range cannot be reversed.

sort [Open Generic Function]


Returns a sequence containing the elements of its argument sequence, sorted.

Signature:

sort source-sequence #key test stable result-sequence

Arguments:
source-sequence

An instance of <sequence>.

test

An instance of <function>. The default is <.

stable

An instance of <object>, treated as a boolean.

Values:
result-sequence

An instance of <sequence>.

Description:

Returns a sequence containing the elements of source-sequence sorted into ascending order. The result-sequence may or may not be freshly allocated. The source-sequence is not modified by this operation.

sort determines the relationship between two elements by giving elements to the test. The first argument to the test function is one element of source-sequence; the second argument is another element of source-sequence. test should return true if and only if the first argument is strictly less than the second (in some appropriate sense). If the first argument is greater than or equal to the second (in the appropriate sense), then the test should return #f.

If stable is supplied and not #f, a possibly slower algorithm will be used that will leave in their original order any two elements, x and y, such that test(x, y) and test(y, x) are both false.

define variable *numbers* = vector(3, 1, 4, 1, 5, 9)
*numbers*
  ⇒ #[3, 1, 4, 1, 5, 9]
sort (*numbers*)
  ⇒  #[1, 1, 3, 4, 5, 9]
*numbers*
  ⇒  #[3, 1, 4, 1, 5, 9]

sort! [Open Generic Function]


Returns a sequence containing the elements of its argument sequence, sorted.

Signature:

sort! source-sequence #key test stable result-sequence

Arguments:
source-sequence

An instance of <sequence>.

test

An instance of <function>. The default is <.

stable

An instance of <object>, treated as a boolean.

Values:
result-sequence

An instance of <sequence>.

Description:

Returns a sequence containing the elements of source-sequence sorted into ascending order. The result-sequence may or may not be freshly allocated. The source-sequence may be modified by this operation. The result-sequence may or may not be == to source-sequence. After this operation, the contents of source-sequence are undefined.

Programs should never rely on this operation performing a side-effect on an existing sequence, but should instead use the value returned by the function.

sort! determines the relationship between two elements by giving elements to the test. The first argument to the test function is one element of source-sequence; the second argument is another element of source-sequence. test should return true if and only if the first argument is strictly less than the second (in some appropriate sense). If the first argument is greater than or equal to the second (in the appropriate sense), then the test should return #f.

If stable is supplied and not #f, a possibly slower algorithm will be used that will leave in their original order any two elements, x and y, such that test(x, y) and test(y, x) are both false.

define variable *numbers* = vector(3, 1, 4, 1, 5, 9)
*numbers*
  ⇒ #[3, 1, 4, 1, 5, 9]
sort! (*numbers*)
  ⇒  #[1, 1, 3, 4, 5, 9]
*numbers*
  ⇒  {undefined}

Set Operations

intersection [Open Generic Function]


Returns the intersection of two sequences.

Signature:

intersection sequence1 sequence2 #key test new-sequence

Arguments:
sequence1

An instance of <sequence>.

sequence2

An instance of <sequence>.

test

An instance of <function>. The default is ==.

Values:
new-sequence

An instance of <sequence>.

Description:

Returns a new sequence containing only those elements of sequence1 that also appear in sequence2.

test is used to determine whether an element appears in sequence2. It is always called with an element of sequence1 as its first argument and an element from sequence2 as its second argument. The order of elements in the result sequence is not specified.

new-sequence may or may not share structure with the sequence1 and sequence2.

? intersection (#("john", "paul", "george", "ringo"),
                #("richard", "george", "edward", "charles"),
                test: \=)
#("george")
intersection range1 range2 #key test range [Sealed G.F. Method]

intersection applied to two ranges and a test of == (the default) will produce another range as its result, even though the type-for-copy of a range is not <range>. If either range1 or range2 is unbounded, this method is guaranteed to terminate only if the test is ==.

union [Open Generic Function]


Returns the union of two sequences.

Signature:

union sequence1 sequence2 #key test new-sequence

Arguments:
sequence1

An instance of <sequence>.

sequence2

An instance of <sequence>.

test

An instance of <function>. The default is ==.

Values:
new-sequence

An instance of <sequence>.

Description:

Returns a sequence containing every element of sequence1 and sequence2.

If the same element appears in both argument sequences, this will not cause it to appear twice in the result sequence. However, if the same element appears more than once in a single argument sequence, it may appear more than once in the result sequence.

test is used for all comparisons. It is always called with an element from sequence1 as its first argument and an element from sequence2 as its second argument. The order of elements in the new-sequence is not specified.

new-sequence may or may not share structure with sequence1 or sequence2.

union (#("butter", "flour", "sugar", "salt", "eggs"),
       #("eggs", "butter", "mushrooms", "onions", "salt"),
       test: \=)
  #("salt", "butter", "flour", "sugar", "eggs",
       "mushrooms", "onions")

remove-duplicates [Open Generic Function]


Returns a sequence without duplicates.

Signature:

remove-duplicates source-sequence #key test result-sequence

Arguments:
source-sequence

An instance of <sequence>.

test

An instance of <function>. The default is ==.

Values:
result-sequence

An instance of <sequence>.

Description:

Returns a sequence that contains all the unique elements from source-sequence but no duplicate elements.

test is the function used to determine whether one element is a duplicate of another. The test argument may be noncommutative; it will always be called with its arguments in the same order as they appear in source-sequence.

The result-sequence may or may not be freshly allocated. However, the source-sequence will not be modified by this operation.

remove-duplicates (#("spam", "eggs", "spam", 
                     "sausage", "spam", "spam"),
                    test: \=)
  #("spam", "eggs", "sausage")
or
  #("eggs", "spam", "sausage")
or
  #("eggs", "sausage", "spam")

remove-duplicates! [Open Generic Function]


Returns a sequence without duplicates.

Signature:

remove-duplicates! source-sequence #key test result-sequence

Arguments:
source-sequence

An instance of <sequence>.

test

An instance of <function>. The default is ==.

Values:
result-sequence

An instance of <sequence>.

Description:

Returns a sequence that contains all the unique elements from source-sequence but no duplicate elements.

test is the function used to determine whether one element is a duplicate of another. The test argument may be noncommutative; it will always be called with its arguments in the same order as they appear in source-sequence.

The result-sequence may or may not be freshly allocated, may or may not share structure with the source-sequence, and may or may not be == to the source-sequence. The source-sequence may or may not be modified by the operation.

define variable *menu* = #("spam", "eggs", "spam", 
                           "sausage", "spam", "spam")
remove-duplicates! (*menu*, test: \=)
  ⇒  #("spam", "eggs", "sausage")
or
  #("eggs", "spam", "sausage")
or
  #("eggs", "sausage", "spam")
*menu*
  ⇒  {undefined}

Subsequence Operations

copy-sequence [Open Generic Function]


Returns a freshly allocated copy of some subsequence of a sequence.

Signature:

copy-sequence source #key start end new-sequence

Arguments:
source

An instance of <sequence>.

start

An instance of <integer>. The default is 0.

end

An instance of <integer>. The default is the size of source.

Values:
new-sequence

A freshly allocated instance of <sequence>.

Description:

Creates a freshly allocated sequence containing the elements of source between start and end.

define constant hamlet = #("to", "be", "or", "not", "to", "be")
hamlet == copy-sequence (hamlet)
  #f
copy-sequence (hamlet, start: 2, end: 4)
  #("or", "not")
copy-sequence range #key start endnew-range [Sealed G.F. Method]

When applied to a range, copy-sequence returns another range, even though the type-for-copy of a range is the <list> class.

concatenate [Function]


Returns the concatenation of one or more sequences in a sequence of a type determined by the type-for-copy of its first argument.

Signature:

concatenate first-sequence #rest more-sequences result-sequence

Arguments:
first-sequence

An instance of <sequence>.

more-sequences

Instances of <sequence>.

Values:
result-sequence

An instance of <sequence>.

Description:

Returns a sequence containing all the elements of all the sequences, in order.

The result-sequence will be an instance of the type-for-copy value for first-sequence. It may or may not be freshly allocated. The result-sequence may be created by calling make on the indicated type, with a size: initialization argument whose value is the sum of the sizes of the argument sequences. (For this reason, the type-for-copy value of first-sequence must support the size: init-keyword.)

new-sequence may share structure with any of the argument sequences, but it is not guaranteed to do so. The argument sequences will not be modified by this operation.

concatenate ("low-", "calorie")
  "low-calorie"

concatenate-as [Function]


Returns the concatenation of one or more sequences in a sequence of a specified type.

Signature:

concatenate-as type first-sequence #rest more-sequences result-sequence

Arguments:
type

An instance of <type>, which must be a subtype of <mutable-sequence>

first-sequence

An instance of <sequence>.

more-sequences

Instances of <sequence>.

Values:
result-sequence

An instance of type, and therefore also an instance of <sequence>.

Description:

Returns a sequence containing all the elements of all the sequences, in order.

The result-sequence will be an instance of type. It may or may not be freshly allocated.

type must be a subtype of <mutable-sequence> and acceptable as the first argument to make. size: with a non-negative integer value must be an acceptable initarg for make of type. The result-sequence may be created by calling make on type, with a size: initialization argument whose value is the sum of the sizes of the arguments.

concatenate-as (<string>, #('n', 'o', 'n'), #('f', 'a', 't'))
  "nonfat"

replace-subsequence! [Open Generic Function]


Replaces a portion of a sequence with the elements of another sequence.

Signature:

replace-subsequence! target-sequence insert-sequence #key start end
result-sequence

Arguments:
target-sequence

An instance of <sequence>.

insert-sequence

An instance of <sequence>.

start

An instance of <integer>. The default is 0.

end

An instance of <integer>. The default is the size of target-sequence.

Values:
result-sequence

An instance of <sequence>.

Description:

replace-subsequence! returns a sequence with the same elements as target-sequence, except that elements of the indicated subsequence of target-sequence are replaced by all the elements of insert-sequence. The subsequence to be overridden begins at index start and ends at index end.

result-sequence may or may not share structure with target-sequence or insert-sequence, and it may or may not be == to target-sequence or insert-sequence. target-sequence may or may not be modified by the operation. insert-sequence will not be modified by this operation.

define variable *original* = list ("a", "b", "c", "d", "e")

*new* := replace-subsequence! (*original*, #("x", "y", "z"), end: 1)
  #("x", "y", "z", "b", "c", "d", "e")

*new* := replace-subsequence! (*new*, #("x", "y", "z"), start: 4)
  #("x", "y", "z", "b", "x", "y", "z")

*new* := replace-subsequence! (*new*, #("a", "b", "c"), 
                                      start: 2, end: 4)
  #("x", "y", "a", "b", "c", "x", "y", "z")

Errata: In the published book, target-sequence is incorrectly written as source-sequence.

Errata: In the published book, each of the example calls of replace-subsequence! ends with an extra right parenthesis.

subsequence-position [Open Generic Function]


Returns the position where a pattern appears in a sequence.

Signature:

subsequence-position big pattern #key test count index

Arguments:
big

An instance of <sequence>.

pattern

An instance of <sequence>.

test

An instance of <function>. The default is ==.

count

An instance of <integer>. The default is 1.

Values:
index

#f or an instance of <integer>.

Description:

Searches big for a subsequence that is element-for-element equal to pattern, as determined by the test argument.

test is applied to elements of successive subsequences of big and corresponding elements of the pattern to determine whether a match has occurred. If a subsequence is found, subsequence-position returns the index at which the subsequence starts; otherwise, it returns #f. If there is more than one match, count determines which subsequence is selected. A count of 1 (the default) indicates that the first match should be returned.

subsequence-position ("Ralph Waldo Emerson", "Waldo")
  6

Mapping and Reducing

Simple Mapping

The following mapping functions (do, map, map-as, map-into, any?, every?) iterate over a number of source collections. Each time through the iteration, a function is applied to one element from each of the source collections. The number of arguments to the function is equal to the number of source collections.

The functions vary in how they handle the results of each function application.

do [Function]


Iterates over one or more collections for side effect.

Signature:

do function collection #rest more-collections false

Arguments:
function

An instance of <function>.

collection

An instance of <collection>.

more-collections

Instances of <collection>.

Values:
false

#f.

Description:

Applies function to corresponding elements of all the collections and returns #f. If all the collections are seque