11. Collections

Like most programming languages, Common Lisp provides standard data types that collect multiple values into a single object. Every language slices up the collection problem a little bit differently, but the basic collection types usually boil down to an integer-indexed array type and a table type that can be used to map more or less arbitrary keys to values. The former are variously called arrays, lists, or tuples; the latter go by the names hash tables, associative arrays, maps, and dictionaries.

Lisp is, of course, famous for its list data structure, and most Lisp books, following the ontogeny-recapitulates-phylogeny principle of language instruction, start their discussion of Lisp’s collections with lists. However, that approach often leads readers to the mistaken conclusion that lists are Lisp’s only collection type. To make matters worse, because Lisp’s lists are such a flexible data structure, it is possible to use them for many of the things arrays and hash tables are used for in other languages. But it’s a mistake to focus too much on lists; while they’re a crucial data structure for representing Lisp code as Lisp data, in many situations other data structures are more appropriate.

To keep lists from stealing the show, in this chapter I’ll focus on Common Lisp’s other collection types: vectors and hash tables.1 However, vectors and lists share enough characteristics that Common Lisp treats them both as subtypes of a more general abstraction, the sequence. Thus, you can use many of the functions I’ll discuss in this chapter with both vectors and lists.