Collections

The defined name of this module is collection. A collection is defined as an instance of one of <list>, <string>, <vector>, <table> or any user-defined class for which a method is added to any of the collection manipulation functions. Collection does not name a class and does not form a part of the class hierarchy. This module defines a set of operators on collections as generic functions and default methods with the behaviours given here.

When iterating over a single collection, the order in which elements are processed might not be important, but as soon as more than one collection is involved, it is necessary to specify how the collections are aligned so that it is clear which elements of the collections will be processed together. This is quite straightforward in the cases of <list>, <string> and <vector>, since there is an intuitive natural order for the elements which allows them to be identified by a non-negative integer. Thus, when iterating over a combination of any of these, all the elements at index position i will be processed together, starting with the elements at position 0 and finishing with those at position n 1 where n is the size of the smallest collection in the combination. The subset of collections which have natural order is called sequence and members of this set can be identified by the predicate sequencep, while collections in general can be identified by collectionp.

Collection alignment is more complicated when tables are involved since they use explicit keys rather than natural order to identify their elements. In any iteration over a combination of collections including a table or some tables, the set of keys used is the intersection of the keys of the tables and the implicit keys of the other collection classes present; this identifies the elements of the collections with common keys. Thus, for an iteration to process any elements from the combination of a collection with natural order and a table, the table must have some integer keys and they must be in the range [0; size) of the collection with natural order.

A conforming level-0 implementation must define methods on these functions to support operations on lists (?? ), strings (?? ), tables (?? ), vector (?? ) and any combination of these.

<collection- condition> : <condition>
This is the condition class for all collection processing conditions.

accumulate : generic-function

Generic arguments

(function <function>)
A function of two arguments.
(obj <object>)
The object which is the initial value for the accumulation operation.
(collection <object>)
The collection which is the subject of the accumulation operation.

Result

The result is the result of the application of function to the accumulated result and successive elements of collection. The initial value of the accumulated result is supplied by obj.

Examples

input:
(accumulate * 1 #(1 2 3 4 5))
output:
120
input:
(accumulate (lambda (a v) (cons v a)) () #(a b c))
output:
(c b a)

accumulate1 : generic-function

Generic arguments

(function <function>)
A function of two arguments.
(collection <object>)
The collection which is the subject of the accumulation operation.

Result

The result is the result of the application of function to the accumulated result and successive elements of collection starting with the second element. The initial value of the accumulated result is the first element of collection. The terms first and second correspond to the appropriate elements of a natural order collection, but no elements in particular of an explicit key collection. If collection is empty, the result is ().

Examples

input:
(accumulate1 (lambda (a v) (if (< a v) a v)) '(4 3 2 9 1 7))
output:
1

anyp : generic-function

Generic arguments

(function <function>)
A function to be used as a predicate on the elements of the collection(s).
(collection <object>)
A collection.
[more-collections]
More collections.

Result

The function is applied to argument lists constructed from corresponding successive elements of collection and more-collections. If the result is true, the result of anyp is true and there are no further applications of function to elements of collection and more-collections. If any of the collections is exhausted, the result of anyp is ().

Examples

input:
(anyp even #(1 2 3 4))
output:
true
input:
(let ((x (list 1 2 3 4))) (anyp > x (cdr x)))
output:
()
input:
(anyp (lambda (a b) (= (% a b) 0)) #(3 2) '(1 0))
output:
true

collectionp : generic-function

Generic arguments

(object <object>)
An object to examine.

Result

Returns true if object is a collection, otherwise ().

Remarks

This predicate does not return object because () is a collection.

concatenate : generic-function

Generic arguments

(collection <object>)
A collection.
[more-collections]
More collections.

Result

The result is an object of the same class as collection.

Remarks

The contents of the result object depend on whether collection has natural order or not:
  1. If collection has natural order then the size of the result is the sum of the sizes of collection and more-collections. The result collection is initialized with the elements of collection followed by the elements of each of more-collections taken in turn. If any element cannot be stored in the result collection, for example, if the result is a string and some element is not a character, an error is signalled (condition class: collection-condition).
  2. If collection does not have natural order, then the result will contain associations for each of the keys in collection and more-collections. If any key occurs more than once, the associated value in the result is the value of the last occurrence of that key after processing collection and each of more-collections taken in turn.

Examples

input:
(concatenate #(1) '(2) "bc")
output:
#(1 2 #\b #\c)
input:
(concatenate "a" '(#\b))
output:
"ab"
input:
(concatenate #() '(a b) "c")
output:
#(a b #\c)

delete : generic-function

Generic arguments

(object <object>)
Object to be removed.
(collection <collection>)
A collection.
[test]
The function to be used to compare object and the elements of collection.

Result

If there is an element of collection such that test returns true when applied to object and that element, then the result is the modified collection, less that element. Otherwise, the result is collection.

Remarks

delete is destructive. The test function defaults to eql.

do : generic-function

Generic arguments

(function <function>)
A function.
(collection <object>)
A collection.
[more-collections]
More collections.

Result

The result is (). This operator is used for side-effect only. The function is applied to argument lists constructed from corresponding successive elements of collection and more-collections and the result is discarded. Application stops if any of the collections is exhausted.

Examples

input:
(do prin '(1 b #\c))
output:
1bc
input:
(do write '(1 b #\c))
output:
1b#\c

element : generic-function

Generic arguments

(collection <object>)
The object to be accessed or updated.
(key <object>)
The object identifying the key of the element in collection.

Result

The value associated with key in collection.

Examples

input:
(element "abc" 1)
output:
#\b
input:
(element '(a b c) 1)
output:
b
input:
(element #(a b c) 1)
output:
b

(setter element) : setter function

Generic arguments

(collection <object>)
The object to be accessed or updated.
(key <object>)
The object identifying the key of the element in collection.
(value <object>)
The object to replace the value associated with key in collection (for setter).

Result

The argument supplied as value, having updated the association of key in collection to refer to value.

emptyp : generic-function

Generic arguments

(collection <object>)
The object to be examined.

Result

Returns true if collection is the object identified with the empty object for that class of collection.

Examples

input:
(emptyp "")
output:
true
input:
(emptyp ())
output:
true
input:
(emptyp #())
output:
true
input:
(emptyp (make <table>))
output:
true

fill : generic-function

Generic arguments

(collection <object>)
A collection to be (partially) filled.
(object <object>)
The object with which to fill collection.
[keys]
The keys with which object is to be associated.

Result

The result is ().

Remarks

This function side-effects collection by updating the values associated with each of the specified keys with obj. If no keys are specified, the whole collection is filled with obj. Otherwise, the key specification can take two forms:
  1. A collection, in which case the values of the collection are taken to be the keys of collection to be associated with obj.
  2. Two fixed precision integers, denoting the start and end keys, respectively, in a natural order collection to be associated with obj. An error is signalled (condition class: collection-condition) if collection does not have natural order. It is an error if the start and end do not specify an ascending sub-interval of the interval [0; size), where size is that of collection.

find-key : generic-function

Generic arguments

(collection <collection>)
A collection.
(test <function>)
A function.
[skip]
An integer.
[failure]
An integer.

Result

The function test is applied to successive elements of collection. If test returns true when applied to an element, then the result of find-key is the key associated with that element.

Remarks

The value skip, which defaults to zero, indicates how many successful tests are to be made before returning a result. The value failure, which defaults to (), is returned if no key satisfying the test was found. Note that skip and failure are positional arguments and that skip must be specified if failure is specified.

first : generic-function

Generic arguments

(sequence <sequence>)
A sequence.

Result

The result is contents of index position 0 of sequence.

key-sequence : generic-function

Generic arguments

(collection <collection>)
A collection.

Result

The result is a collection comprising the keys of collection.

map : generic-function

Generic arguments

(function <function>)
A function.
(collection <object>)
A collection.
[more-collections]
More collections.

Result

The result is an object of the same class as collection. The elements of the result are computed by the application of function to argument lists constructed from corresponding successive elements of collection and more-collections. Application stops if any of the collections is exhausted.

Examples

input:
(map cons #(1 2) '(3))
output:
#((1 . 3))
input:
(map (lambda (f) (f 1 2)) (+ - * %))
output:
#(3 -1 2 1)

member : generic-function

Generic arguments

(object <object>)
The object to be searched for in collection.
(collection <object>)
The collection to be searched.
[test]
The function to be used to compare object and the elements of collection.

Result

Returns true if there is an element of collection such that the result of the application of test to object and that element is true. If test is not supplied, eql is used by default. Note that true denotes any value that is not () and that the class of the result depends on the class of collection. In particular, if collection is a list, the result of member is a list.

Examples

input:
(member #\b "abc")
output:
true
input:
(member 'b '(a b c))
output:
(b c)
input:
(member 'b #(a b c))
output:
true

remove : generic-function

Generic arguments

(object <object>)
Object to be removed.
(collection <collection>)
A collection.
[test]
The function to be used to compare object and the elements of collection.

Result

If there is an element of collection such that test returns true when applied to object and that element, then the result is a shallow copy of collection less that element. Otherwise, the result is collection.

Remarks

The test function defaults to eql.

reverse : generic-function

Generic arguments

(collection <object>)
A collection.

Result

The result is an object of the same class as collection whose elements are the same as those in collection, but in the reverse order with respect to the natural order of collection. If collection does not have natural order, the result is equal to the argument.

Examples

input:
(reverse "abc")
output:
"cba"
input:
(reverse '(1 2 3))
output:
(3 2 1)
input:
(reverse #(a b c))
output:
#(c b a)

second : generic-function

Generic arguments

(sequence <sequence>)
A sequence.

Result

The result is contents of index position 1 of sequence.

sequencep : generic-function

Generic arguments

(object <object>)
An object to examine.

Result

Returns true if object is a sequence (has natural order), otherwise ().

Remarks

This predicate does not return object because () is a sequence.

size : generic-function

Generic arguments

(collection <object>)
The object to be examined.

Result

An integer which denotes the size of collection according to the method for the class of collection.

Examples

input:
(size "")
output:
0
input:
(size ())
output:
0
input:
(size #())
output:
0
input:
(size (make <table>))
output:
0
input:
(size "abc")
output:
3
input:
(size (cons 1 ()))
output:
1
input:
(size (cons 1 . 2))
output:
1
input:
(size (cons 1 (cons 2 . 3)))
output:
2
input:
(size '(1 2 3))
output:
3
input:
(size #(a b c))
output:
3

sort : generic-function

Generic arguments

(sequence <sequence>)
A sequence.
(comparator <function>)
A function.

Result

The result of sort is a new sequence comprising the elements of sequence ordered according to comparator.

Remarks

Methods on this function are only defined for <list> and <vector>.

third : generic-function

Generic arguments

(sequence <sequence>)
A sequence.

Result

The result is contents of index position 2 of sequence.

(converter <list>) : class

Specialized arguments

(collection <object>)
A collection to be converted into a list.

Result

If collection is a list, the result is the argument. Otherwise a list is constructed and returned whose elements are the elements of collection. If collection has natural order, then the elements will appear in the result in the same order as in collection. If collection does not have natural order, the order in the resulting list is undefined.

See also:

Conversion (?? ).

(converter <string>) : class

Specialized arguments

(collection <object>)
A collection to be converted into a string.

Result

If collection is a string, the result is the argument. Otherwise a string is constructed and returned whose elements are the elements of collection as long as all the elements of collection are characters. An error is signalled (condition class: conversion-condition) if any element of collection is not a character. If collection has natural order, then the elements will appear in the result in the same order as in collection. If collection does not have natural order, the order in the resulting string is undefined.

See also:

Conversion (?? ).

(converter <table>) : class

Specialized arguments

(collection <object>)
A collection to be converted into a table.

Result

If collection is a table, the result is the argument. Otherwise a table is constructed and returned whose elements are the elements of collection. If collection has natural order, then the elements will be stored under integer keys in the range [0:::size), otherwise the keys used will be the keys associated with the elements of collection.

See also:

Conversion (?? ).

(converter <vector>) : class

Specialized arguments

(collection <object>)
A collection to be converted into a vector.

Result

If collection is a vector, the result is the argument. Otherwise a vector is constructed and returned whose elements are the elements of collection. If collection has natural order, then the elements will appear in the result in the same order as in collection. If collection does not have natural order, the order in the resulting vector is undefined.

See also:

Conversion (?? ).
Julian Padget, jap@maths.bath.ac.uk, this version December 21, 1994