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? collection ⇒ boolean [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 collection ⇒ integer-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 array ⇒ size [G.F. Method]

The method for <array> is equivalent to

reduce(\*, 1, dimensions (array))
size list ⇒ integer-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 range ⇒ size [Sealed G.F. Method]

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

size table ⇒ size [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 array ⇒ rank [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 subscripts ⇒ index [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 vector ⇒ sequence [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 axis ⇒ dimension [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 sequence ⇒ test-function [Sealed G.F. Method]

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

key-test table ⇒ test-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 default ⇒ element [Sealed G.F. Method]

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

element unicode-string index #key default ⇒ character [Sealed G.F. Method]

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

element byte-string index #key default ⇒ character [Sealed G.F. Method]

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

element table key #key default ⇒ element [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 index ⇒ character [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 indices ⇒ element [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 indices ⇒ new-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 count ⇒ deque [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 count ⇒ list [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 range ⇒ new-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! range ⇒ range [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 end ⇒ new-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 sequences, do guarantees that they will be processed in their natural order.

do (method (a b) print (a + b) end,
    #(100, 100, 200, 200),
    #(1, 2, 3, 4))
101
102
203
204
 ⇒  #f

map [Function]

Iterates over one or more collections and collects the results in a freshly allocated collection.

Signature:

map function collection #rest more-collections ⇒ new-collection

Arguments:
function

An instance of <function>.

collection

An instance of <collection>.

more-collections

Instances of <collection>.

Values:
new-collection

A freshly allocated instance of <collection>.

Description:

Creates a freshly allocated collection whose elements are obtained by calling function on corresponding elements of all the collections. If all the collections are sequences, processing is performed in the natural order.

map returns a collection whose value is an instance of the type-for-copy value of collection. The new collection is created by calling make on that type, with a size: initialization argument whose value is the number of corresponding elements in the collections.

map (\+,
     #(100, 100, 200, 200),
     #(1, 2, 3, 4))
 ⇒  #(101, 102, 203, 204)

map-as [Function]

Iterates over one or more collections and collects the results in a freshly allocated collection of a specified type.

Signature:

map-as type function collection #rest more-collections ⇒ new-collection

Arguments:
type

An instance of <type>. It must be an instantiable subtype of <mutable-collection>.

function

An instance of <function>.

collection

An instance of <collection>.

more-collections

Instances of <collection>.

Values:
new-collection

A freshly allocated instance of <mutable-collection>.

Description:

Creates a freshly allocated collection of type type whose elements are obtained by applying function to corresponding elements of the collection arguments. type must be acceptable as the first argument to make. size: with a non-negative integer value must be an acceptable initarg for make of type. new-collection is created by calling make on type, with a size: initialization argument whose value is the number of corresponding elements in the collections. If all the collections are sequences (including new-collection), processing is done in the natural order.

map-as (<vector>, \+,
        #(100, 100, 200, 200),
        #(1, 2, 3, 4))
 ⇒  #[101, 102, 203, 204]

Errata: In the published book, the result is incorrectly written as a list instead of a vector: #(101, 102, 203, 204)

map-into [Function]

Iterates over one or more collections and collects the results in an existing mutable collection.

Signature:

map-into mutable-collection function collection #rest more-collections
⇒ mutable-collection

Arguments:
mutable-collection

An instance of <mutable-collection>.

function

An instance of <function>.

collection

An instance of <collection>.

more-collections

Instances of <collection>.

Values:
mutable-collection

An instance of <mutable-collection>.

Description:

Returns the mutable-collection argument after modifying it by replacing its elements with the results of applying function to corresponding elements of collection and more-collections.

If mutable-collection and all the other collections are sequences, processing is done in the natural order.

When mutable-collection is an instance of <stretchy-collection>, the usual alignment requirement (described in Collection Alignment on page 120) is relaxed. In this case, the key sequence of mutable-collection is not considered during alignment. Rather, only the key sequences for the source collections are aligned, with function called on the corresponding elements. The result of each call to function is then stored into mutable-collection with the corresponding key (possibly stretching mutable-collection in the process), using element-setter. Other keys in mutable-collection remain undisturbed.

mutable-collection may be the same object as collection or any of the more-collections.

An error is signaled if mutable-collection does not have the same key-test function as the rest of the collections. This is true even if it is a <stretchy-collection> and therefore does not get aligned.

define variable x = list (10, 9, 8, 7)
map-into (x, \+, #(1, 2, 3, 4), #(100, 100, 200, 200))
 ⇒  #(101, 102, 203, 204)
x
 ⇒  #(101, 102, 203, 204)

any? [Function]

Returns the first true value obtained by iterating over one or more collections.

Signature:

any? function collection #rest more-collections ⇒ value

Arguments:
function

An instance of <function>.

collection

An instance of <collection>.

more-collections

Instances of <collection>.

Values:
value

An instance of <object>.

Description:

Applies function to groups of corresponding elements of collection and more-collections. If an application of function returns true, then any? returns that true value. Otherwise function returns #f when applied to every such group, and any? returns #f.

If all the collections are sequences, any? operates in natural order. In all cases, any? stops on the first true value returned by function.

any? (\>, #(1, 2, 3 ,4), #(5, 4, 3, 2))
 ⇒  #t
any? (even?, #(1, 3, 5, 7))
 ⇒  #f

every? [Function]

Returns true if a predicate returns true when applied to all corresponding elements of a set of collections.

Signature:

every? function collection #rest more-collections ⇒ value

Arguments:
function

An instance of <function>.

collection

An instance of <collection>.

more-collections

Instances of <collection>.

Values:
value

An instance of <boolean>.

Description:

Applies function to groups of corresponding elements of collection and more-collections. If an application of function returns false, then every? returns #f. Otherwise function returns a true value when applied to every such group, and every? returns #t.

If all the collections are sequences, every? operates in natural order. In all cases, every? stops on the first false value returned by function.

every? (\>, #(1, 2, 3, 4), #(5, 4, 3, 2))
 ⇒  #f
every? (odd?, #(1, 3, 5, 7))
 ⇒  #t

Extensible Mapping Functions

reduce [Open Generic Function]

Combines the elements of a collection and a seed value into a single value by repeatedly applying a binary function.

Signature:

reduce function initial-value collection ⇒ value

Arguments:
function

An instance of <function>.

initial-value

An instance of <object>.

collection

An instance of <collection>.

Values:
value

An instance of <object>.

Description:

Returns the result of combining the elements of collection and initial-value according to function.

If collection is empty, reduce returns initial-value; otherwise, function is applied to initial-value and the first element of collection to produce a new value. If more elements remain in the collection, then function is called again, this time with the value from the previous application and the next element from collection. This process continues until all elements of collection have been processed.

function is a binary function used to combine all the elements of collection into a single value. Processing is always done in the natural order for collection.

define variable high-score = 10
reduce (max, high-score, #(3, 1, 4, 1, 5, 9))
 ⇒  10
reduce (max, high-score, #(3, 12, 9, 8, 8, 6))
 ⇒  12

reduce1 [Open Generic Function]

Combines the elements of a collection into a single value by repeatedly applying a binary function, using the first element of the collection as the seed value.

Signature:

reduce1 function collection ⇒ value

Arguments:
function

An instance of <function>.

collection

An instance of <collection>.

Values:
value

An instance of <object>.

Description:

Returns the combination of the elements of collection according to function.

An error is signaled if collection is empty.

reduce1 is similar to reduce, except that the first element of collection is taken as the initial value, and all the remaining elements of collection are processed as if by reduce. (In other words, the first value isn't used twice.)

For unstable collections, first element effectively means an element chosen at random. Processing is done in the natural order for collection.

reduce1 (\+, #(1, 2, 3, 4, 5))
 ⇒  15

choose [Open Generic Function]

Returns those elements of a sequence that satisfy a predicate.

Signature:

choose predicate source-sequence ⇒ result-sequence

Arguments:
predicate

An instance of <function>.

source-sequence

An instance of <sequence>.

Values:
result-sequence

An instance of <sequence>.

Description:

Returns a sequence containing those elements of source-sequence that satisfy predicate. The result-sequence may or may not be freshly allocated.

choose (even?, #(3, 1, 4, 1, 5, 8, 9))
  ⇒  #(4, 8)

choose-by [Open Generic Function]

Returns those elements of a sequence that correspond to those in another sequence that satisfy a predicate.

Signature:

choose-by predicate test-sequence value-sequence ⇒ result-sequence

Arguments:
predicate

An instance of <function>.

test-sequence

An instance of <sequence>.

value-sequence

An instance of <sequence>.

Values:
result-sequence

An instance of <sequence>.

Description:

Returns a sequence containing the elements from value-sequence that correspond to elements in test-sequence that satisfy predicate. The result-sequence may or may not be freshly allocated.

choose-by (even?, range (from: 1),
             #("a", "b", "c", "d", "e", "f", "g", "h", "i"))
  ⇒  #("b", "d", "f", "h")

Other Mapping Functions

member? [Open Generic Function]

Returns true if a collection contains a particular value.

Signature:

member? value collection #key test ⇒ boolean

Arguments:
value

An instance of <object>.

collection

An instance of <collection>.

test

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

Values:
boolean

An instance of <boolean>.

Description:

Returns true if collection contains value as determined by test. Otherwise returns false.

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

define constant flavors = #(#"vanilla", #"pistachio", #"ginger")
member? (#"vanilla", flavors)
 ⇒  #t 
member? (#"banana", flavors)
 ⇒  #f
member? val range #key test ⇒ boolean [Sealed G.F. Method]

If range is unbounded, this method is guaranteed to terminate if test is ==.

find-key [Open Generic Function]

Returns the key in a collection such that the corresponding collection element satisfies a predicate.

Signature:

find-key collection predicate #key skip failure ⇒ key

Arguments:
collection

An instance of <collection>.

predicate

An instance of <function>.

skip

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

failure

An instance of <object>. The default is #f.

Values:
key

An instance of <object>.

Description:

Returns a key value such that (predicate (element collection key)) is true. If no element in collection satisfies predicate, find-key returns failure.

The skip argument indicates that the first skip matching elements should be ignored. If skip or fewer elements of collection satisfy predicate, then failure is returned. If collection is not stable under iteration, then skip is only useful for finding out whether collection contains at least skip elements which satisfy predicate; it is not useful for finding a particular element.

flavors
 ⇒  #(#"vanilla", #"pistachio", #"ginger")
find-key (flavors, has-nuts?)
 ⇒  1
flavors[1]
 ⇒  #"pistachio"

Errata: In the published book, the argument predicate is incorrectly named function in the signature of find-key.

remove-key! [Open Generic Function]

Modifies an explicit key collection so it no longer has a particular key.

Signature:

remove-key! collection key ⇒ boolean

Arguments:
collection

An instance of <mutable-explicit-key-collection>.

key

An instance of <object>.

Values:
boolean

An instance of <boolean>.

Description:

Modifies collection so that it no longer has a key equal to key. Equality is determined by collection's key-test function.

The boolean return value will be #t if the key was present and removed, or #f if the key was not present and hence not removed.

remove-key! table key ⇒ table [Sealed G.F. Method]

There is a predefined method on <table>.

replace-elements! [Open Generic Function]

Replaces those collection elements that satisfy a predicate.

Signature:

replace-elements! mutable-collection predicate new-value-fn #key count
⇒ mutable-collection

Arguments:
mutable-collection

An instance of <mutable-collection>.

predicate

An instance of <function>.

new-value-fn

An instance of <function>.

count

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

Values:
mutable-collection

An instance of <mutable-collection>.

Description:

Replaces those elements of mutable-collection for which predicate returns true. The elements are replaced with the value of calling new-value-fn on the existing element. If count is #f, all of the matching elements are replaced. Otherwise, no more than count elements are replaced.

mutable-collection may be modified by this operation.

define variable numbers = list (10, 13, 16, 19)
replace-elements! (numbers, odd?, double)
 ⇒  #(10, 26, 16, 38)

fill! [Open Generic Function]

Fills a collection with a specified value.

Signature:

fill! mutable-collection value #key start end ⇒ mutable-collection

Arguments:
mutable-collection

An instance of <mutable-collection>.

value

An instance of <object>.

start

An instance of <integer>.

end

An instance of <integer>.

Values:
mutable-collection

An instance of <mutable-collection>.

Description:

Modifies mutable-collection so that element(mutable-collection, key) returns value for every key.

If mutable-collection is a sequence, then start and end keywords may be specified to indicate that only a part of the sequence should be filled. start is considered an inclusive bound and defaults to 0; end is an exclusive bound and defaults to the length of the sequence.

define variable numbers = list (10, 13, 16, 19)
fill! (numbers, 3, start: 2)
 ⇒  #(10, 13, 3, 3)

The Iteration Protocol

forward-iteration-protocol [Open Generic Function]

Returns a group of functions used to iterate over the elements of a collection.

Signature:

forward-iteration-protocol collection
⇒ initial-state limit next-state finished-state? current-key current-element current-element-setter copy-state

Arguments:
collection

An instance of <collection>.

Values:
initial-state

An instance of <object>. The initial iteration state object.

limit

An instance of <object> that is used by the finished-state? function to determine whether the iteration has been completed.

next-state

An instance of <function>. Its signature is

next-state collection state ⇒ new-state

This function steps the iteration by producing a new state from the associated collection and state. The next-state function may or may not modify the state argument; it is an error to use a state value after it has been passed to the associated next-state function. The copy-state function provides a mechanism for saving a particular state in an iteration for later resumption.

finished-state?

An instance of <function>. Its signature is

finished-state? collection state limit ⇒ boolean

This function returns #t if the iteration of the collection has been completed, i.e., there are no other elements of the collection to consider. It returns #f otherwise. It is an error to use a finished state in a call to the associated next-state, current-element, current-key or current-element-setter functions.

current-key

An instance of <function>. Its signature is

current-key collection state ⇒ key

This function returns the unique key associated with state in the collection. If the current-key function were called once with each state value produced during an iteration over a collection, the resulting sequence of values would contain every key from the collection exactly once; it would be the key-sequence of the collection.

current-element

An instance of <function>. Its signature is

current-element collection state ⇒ element

This function returns the element of collection currently indicated by state.

current-element-setter

An instance of <function>. Its signature is

current-element-setter value collection state ⇒ value

This function sets the element of collection indicated by state to value and returns value. If collection is not an instance of <mutable-collection>, or if the value is not of a type acceptable to the collection, an error is signaled.

copy-state

An instance of <function>. Its signature is

copy-state collection state ⇒ new-state

This function returns a state that represents the same point in the iteration over collection as is represented by state.

Description:

Returns eight values used to implement iteration over the collection argument.

Only the collection argument this function was called with may be used as the collection argument to functions returned by this function. Only the initial-state object and state objects returned by the next-state and copy-state functions may be used as the state argument to functions returned by this function. Only the limit object may be used as the limit argument to the finished-state? function.

An example of the use of the iteration protocol is the following definition of a single-argument version of the do function:

define method do1 (f :: <function>, c :: <collection>)
  let (init, limit, next, end?, key, elt) =
                     forward-iteration-protocol(c);
  for (state = init then next(c, state),
     until: end?(c, state, limit))
    f(elt(c, state));
  end for;
end method do1;
forward-iteration-protocol table
⇒ initial-state limit next-state finished-state? current-key current-element current-element-setter copy-state [Sealed G.F. Method]

The method for <table> implements the iteration protocol in terms of the function table-protocol.

backward-iteration-protocol [Open Generic Function]

Returns a group of functions used to iterate over the elements of a collection in reverse order.

Signature:

backward-iteration-protocol collection
⇒ initial-state limit next-state finished-state? current-key current-element current-element-setter copy-state

Arguments:
collection

An instance of <collection>.

Values:
initial-state

An instance of <object>.

limit

An instance of <object>.

next-state

An instance of <function>.

finished-state?

An instance of <function>.

current-key

An instance of <function>.

current-element

An instance of <function>.

current-element-setter

An instance of <function>.

copy-state

An instance of <function>.

Description:

Returns eight values used to implement reverse iteration over the collection argument.

Some collection classes that are stable under iteration support the ability to iterate in the reverse of the natural order, by providing a method on the generic function backward-iteration-protocol. The eight values returned by this function are analogous to the corresponding values returned by forward-iteration-protocol.

The Table Protocol

The class <table> provides an implementation of the iteration protocol, using the function table-protocol. Every concrete subclass of <table> must provide or inherit a method for table-protocol. A complete description of the table protocol is given in Tables on page 122.

table-protocol [Open Generic Function]

Returns functions used to implement the iteration protocol for tables.

Signature:

table-protocol table ⇒ test-function hash-function

Arguments:
table

An instance of <table>.

Values:
test-function

An instance of <function>. Its signature is

test-function key1 key2 ⇒ boolean

test-function is used to compare keys. It returns true if the keys are members of the same equivalence class according to the table's equivalence predicate.

hash-function

An instance of <function>. Its signature is

hash-function key ⇒ id state

hash-function computes the hash code of the key, using the hash function associated with the table's equivalence predicate. The hash code is returned as two values, id (an integer) and state (a hash state).

Description:

Returns the test-function and hash-function for the <table>. These functions are in turn used to implement the other collection operations on <table>.

table-protocol object-table ⇒ test-function hash-function [Sealed G.F. Method]

The method for <object-table> returns == as the test-function and object-hash as the hash-function.

The method for <object-table> could be written as

define method table-protocol (table :: <object-table>)
      => (test-function :: <function>, 
          hash-function :: <function>)
  values(\==, object-hash);
end method table-protocol;

Errata: In the published book, the table-protocol method signature is missing parentheses around the result values.

merge-hash-codes [Function]

Returns a hash-code created from the merging of two argument hash codes.

Signature:

merge-hash-codes id1 state1 id2 state2 #key ordered ⇒ merged-id merged-state

Arguments:
id1

An instance of <integer>.

state1

An instance of <object>.

id2

An instance of <integer>.

state2

An instance of <object>.

ordered

An instance of <boolean>.

Values:
merged-id

An instance of <integer>.

merged-state

An instance of <object>.

Description:

Computes a new hash code by merging the argument hash codes in some implementation dependent way. This can be used, for example, to generate a hash-code for an object by combining hash codes of some of its parts.

id1, id2, and merged-id are all integers. state1, state2, and merged-state are all hash states. ordered is a boolean and determines whether the algorithm used to perform the merge is permitted to be order dependent. If false, which is the default, then the merged result must be independent of the order in which the argument pairs are provided. If true, then the order of the argument pairs matters because the algorithm used need not be either commutative or associative. It is best to provide a true value for ordered when possible, as this may result in a better distribution of hash ids. However, ordered must only be true if this will not cause the hash function to violate the second constraint on hash functions, described on page 123.

state1 and state2 should be the value of $permanant-hash-state or hash-states returned from previous calls to merge-hash-codes or object-hash.

object-hash [Function]

The hash function for the equivalence predicate ==.

Signature:

object-hash object ⇒ hash-id hash-state

Arguments:
object

An instance of <object>.

Values:
hash-id

An instance of <integer>.

hash-state

An instance of <object>.

Description:

Returns a hash-code for object that corresponds to the equivalence predicate ==. It is made available as a tool for writing hash functions in which the object identity of some component of a key is to be used in computing the hash code. It returns a hash id (an integer) and associated hash state for the object, computed in some implementation dependent manner. The values returned by object-hash when called repeatedly on the same object might not be the same for each call. If the hash-id value changes then the hash-state value will also change.