9.2: The Varieties of Collections

To make good use of the collection classes, the reader needs at least a superficial knowledge of the wide variety of collections that they implement, and their commonalities and differences.

Programming with collections rather than individual elements is an important way to raise the level of abstraction of a program. The Lisp function map, which applies an argument function to every element of a list and returns a new list containing the results is an early example of this style, but Smalltalk-80 adopted collection-based programming as a central tenet. Modern functional programming languages such as ML and Haskell have followed Smalltalk’s lead.

Why is this a good idea? Suppose you have a data structure containing a collection of student records, and wish to perform some action on all of the students that meet some criterion. Programmers raised to use an imperative language will immediately reach for a loop. But the Smalltalk programmer will write:

students select: [ :each | each gpa < threshold ]

which evaluates to a new collection containing precisely those elements of students for which the bracketed function returns true.¹ The Smalltalk code has the simplicity and elegance of a domain-specific query language.

The message select: is understood by all collections in Smalltalk. There is no need to find out if the student data structure is an array or a linked list: the select: message is understood by both. Note that this is quite different from using a loop, where one must know whether students is an array or a linked list before the loop can be set up.

In Smalltalk, when one speaks of a collection without being more specific about the kind of collection, one means an object that supports well-defined protocols for testing membership and enumerating the elements. All collections understand the testing messages includes:, isEmpty and occurrencesOf:. All collections understand the enumeration messages do:, select:, reject: (which is the opposite of select:), collect: (which is like lisp’s map), detect:ifNone:, inject:into: (which performs a left fold) and many more. It is the ubiquity of this protocol, as well as its variety, that makes it so powerful.

Table \(\PageIndex{1}\): Standard Collection protocols.

Protocol	Methods
accessing	size, capacity, at: anIndex, at: anIndex put: anElement
testing	isEmpty, includes: anElement, contains: aBlock, occurrencesOf: anElement
adding	add: anElement, addAll: aCollection
removing	remove: anElement, remove: anElement ifAbsent: aBlock, removeAll: aCollection
enumerating	do: aBlock, collect: aBlock, select: aBlock, reject: aBlock, detect: aBlock, detect: aBlock ifNone: aNoneBlock, inject: aValue into: aBinaryBlock
converting	asBag, asSet, asOrderedCollection, asSortedCollection, asArray, asSortedCollection: aBlock
creation	with: anElement, with:with:, with:with:with:, with:with:with:with:, withAll: aCollection

Table \(\PageIndex{1}\) summarizes the standard protocols supported by most of the classes in the collection hierarchy. These methods are defined, redefined, optimized or occasionally even forbidden by subclasses of Collection.

Beyond this basic uniformity, there are many different kinds of collection either supporting different protocols, or providing different behaviour for the same requests. Let us briefly survey some of the key differences:

• Sequenceable: Instances of all subclasses of SequenceableCollection start from a first element and proceed in a well-defined order to a last element. Instances of Set, Bag and Dictionary, on the other hand, are not sequenceable.

• Sortable: A SortedCollection maintains its elements in sort order.

• Indexable: Most sequenceable collections are also indexable, that is, elements can be retrieved with at:. Array is the familiar indexable data structure with a fixed size; anArray at: n retrieves the n^th element of anArray, and anArray at: n put: v changes the n^th element to v. LinkedLists and SkipLists are sequenceable but not indexable, that is, they understand first and last, but not at:.

• Keyed: Instances of Dictionary and its subclasses are accessed by keys instead of indices.

• Mutable: Most collections are mutable, but Intervals and Symbols are not. An Interval is an immutable collection representing a range of Integers. For example, 5 to: 16 by: 2 is an interval that contains the elements 5, 7, 9, 11, 13 and 15. It is indexable with at:, but cannot be changed with at:put:.

• Growable: Instances of Interval and Array are always of a fixed size. Other kinds of collections (sorted collections, ordered collections, and linked lists) can grow after creation.

• Accepts duplicates: A Set will filter out duplicates, but a Bag will not. Dictionary, Set and Bag use the = method provided by the elements; the Identity variants of these classes use the == method, which tests whether the arguments are the same object, and the Pluggable variants use an arbitrary equivalence relation supplied by the creator of the collection.

• Heterogeneous: Most collections will hold any kind of element. A String, CharacterArray or Symbol, however, only holds Characters. An Array will hold any mix of objects, but a ByteArray only holds Bytes, an IntegerArray only holds Integers and a FloatArray only holds Floats. A LinkedList is constrained to hold elements that conform to the Link ⊳ accessing protocol.

---

1. The expression in brackets can be thought of as a λ-expression defining an anonymous function λx.x gpa < threshold.