Hash Table Iteration

Common Lisp provides a couple ways to iterate over the entries in a hash table. The simplest of these is via the function **MAPHASH**. Analogous to the **MAP** function, **MAPHASH** takes a two-argument function and a hash table and invokes the function once for each key/value pair in the hash table. For instance, to print all the key/value pairs in a hash table, you could use **MAPHASH** like this:

(maphash #'(lambda (k v) (format t "~a => ~a~%" k v)) *h*)

The consequences of adding or removing elements from a hash table while iterating over it aren’t specified (and are likely to be bad) with two exceptions: you can use **SETF** with **GETHASH** to change the value of the current entry, and you can use **REMHASH** to remove the current entry. For instance, to remove all the entries whose value is less than ten, you could write this:

(maphash #'(lambda (k v) (when (< v 10) (remhash k *h*))) *h*)

The other way to iterate over a hash table is with the extended **LOOP** macro, which I’ll discuss in Chapter 22.12 The **LOOP** equivalent of the first **MAPHASH** expression would look like this:

(loop for k being the hash-keys in *h* using (hash-value v)
  do (format t "~a => ~a~%" k v))

I could say a lot more about the nonlist collections supported by Common Lisp. For instance, I haven’t discussed multidimensional arrays at all or the library of functions for manipulating bit arrays. However, what I’ve covered in this chapter should suffice for most of your general-purpose programming needs. Now it’s finally time to look at Lisp’s eponymous data structure: lists.

1Once you’re familiar with all the data types Common Lisp offers, you’ll also see that lists can be useful for prototyping data structures that will later be replaced with something more efficient once it becomes clear how exactly the data is to be used.

2Vectors are called vectors, not arrays as their analogs in other languages are, because Common Lisp supports true multidimensional arrays. It’s equally correct, though more cumbersome, to refer to them as one-dimensional arrays.

3Array elements “must” be set before they’re accessed in the sense that the behavior is undefined; Lisp won’t necessarily stop you.

4While frequently used together, the :fill-pointer and :adjustable arguments are independent—you can make an adjustable array without a fill pointer. However, you can use **VECTOR-PUSH** and **VECTOR-POP** only with vectors that have a fill pointer and **VECTOR-PUSH-EXTEND** only with vectors that have a fill pointer and are adjustable. You can also use the function **ADJUST-ARRAY** to modify adjustable arrays in a variety of ways beyond just extending the length of a vector.

5Another parameter, :test-not parameter, specifies a two-argument predicate to be used like a :test argument except with the boolean result logically reversed. This parameter is deprecated, however, in preference for using the **COMPLEMENT** function. **COMPLEMENT** takes a function argu-ment and returns a function that takes the same number of arguments as the original and returns the logical complement of the original function. Thus, you can, and should, write this:

(count x sequence :test (complement #'some-test))

rather than the following:

(count x sequence :test-not #'some-test)

6Note, however, that the effect of :start and :end on **REMOVE** and **SUBSTITUTE** is only to limit the elements they consider for removal or substitution; elements before :start and after :end will be passed through untouched.

7This same functionality goes by the name grep in Perl and filter in Python.

8The difference between the predicates passed as :test arguments and as the function arguments to the -IF and -IF-NOT functions is that the :test predicates are two-argument predicates used to compare the elements of the sequence to the specific item while the -IF and -IF-NOT predicates are one-argument functions that simply test the individual elements of the sequence. If the vanilla variants didn’t exist, you could implement them in terms of the -IF versions by embedding a specific item in the test function.

(count char string) ===
  (count-if #'(lambda (c) (eql char c)) string)

(count char string :test #'CHAR-EQUAL) ===
  (count-if #'(lambda (c) (char-equal char c)) string)

9If you tell **CONCATENATE** to return a specialized vector, such as a string, all the elements of the argument sequences must be instances of the vector’s element type.

10When the sequence passed to the sorting functions is a vector, the “destruction” is actually guaranteed to entail permuting the elements in place, so you could get away without saving the returned value. However, it’s good style to always do something with the return value since the sorting functions can modify lists in much more arbitrary ways.

11By an accident of history, the order of arguments to **GETHASH** is the opposite of **ELT**--**ELT** takes the collection first and then the index while **GETHASH** takes the key first and then the collection.

12**LOOP**‘s hash table iteration is typically implemented on top of a more primitive form, **WITH-HASH-TABLE-ITERATOR**, that you don’t need to worry about; it was added to the language specifically to support implementing things such as **LOOP** and is of little use unless you need to write completely new control constructs for iterating over hash tables.