Chapter 8

Collections

Element Types

Each instance X of <collection> has a conceptual element type that is an instance of <type>. If the element type of X is T, X stores elements of type T. The element method will always return an instance of T and the element-setter method (if X is mutable) will accept any instance of T. The analogous functions returned by the iteration protocol also return/accept any instance of T.

Each subclass C of <collection> has a conceptual element type that is either T1 or indefinite ⇐ T1, where T1 is a type. (The symbol ⇐ in the indefinite ⇐ T1 notation is an abbreviation for subtype.)

If the element type of C is T1, each general instance of C must have an element type T2 that is type equivalent to T1. Each subclass of C must have an element type T3 that is type equivalent to T1.

If the element type of C is indefinite ⇐ T1, each general instance of C must have an element type T2 that is a subtype of T1. Therefore, element called on that instance will return an instance of T1 (and will not return all possible instances of T1 if T2 is a proper subtype of T1). It is not determined by C what the applicable element-setter method will accept (thus C's element type is said to be indefinite). Each subclass of C must have element type T3 or indefinite ⇐ T3, where T3 is a subtype of T1.

User-defined collection classes must also follow these rules.

Note: the above statements about the value returned by element only apply when no default: keyword argument is specified.

Table 8-1 Element Types of Built-in Collections

Collection

Element Type

<collection>

indefinite ⇐ <object>

<explicit-key-collection>

indefinite ⇐ <object>

<mutable-collection>

indefinite ⇐ <object>

<stretchy-collection>

indefinite ⇐ <object>

<sequence>

indefinite ⇐ <object>

<mutable-explicit-key-collection>

indefinite ⇐ <object>

<mutable-sequence>

indefinite ⇐ <object>

<table>

indefinite ⇐ <object>

<object-table>

indefinite ⇐ <object>

<array>

indefinite ⇐ <object>

<vector>

indefinite ⇐ <object>

<simple-vector>

indefinite ⇐ <object>

<stretchy-vector>

indefinite ⇐ <object>

<deque>

indefinite ⇐ <object>

<string>

indefinite ⇐ <character>

<range>

indefinite ⇐ <real>

<simple-object-vector>

<object>

<unicode-string>

K1 (see note below)

<byte-string>

K2 (see note below)

<list>

<object>

<pair>

<object>

<empty-list>

<object>

Note: K1 and K2 are subtypes of <character> that have not been given standardized names.

By convention, if C is an instantiable subtype of <collection> and C's element-type is indefinite ⇐ <object>, then instantiating C produces a collection whose element type is <object>.

Instantiating <range> produces a collection whose element-type is unspecified except that it is a subtype of <real> and every element of the range is an instance of the element type.

The preceding section describes the element type of every object that is created by make of an instantiable built-in collection class. The element type of an instance of a user-defined collection class is unspecified, but should follow the rules given here in order to preserve the property that any operation that works on an instance of a supertype must work on an instance of a subtype.