Drinkable Chicken

Python has a separate dictionary type. I'm assuming most of my readers are familiar with it, as it's very common; if not, please read the fine tutorial first, followed by the library reference.

In short, Python's dictionaries are mutable objects that associate unique keys with values. There is special syntax to create them.

Now, going by R5RS, Scheme doesn't even have anything similar. All it has is three closely related functions, that look up pairs in a list, based on a "key" which is matched to the first element of each pair. These functions are assq, assv and assoc. (See here in R5RS.)

Naturally, it's possible to write extensions in Scheme that look more like Python's dict (or Ruby's Hash, etc), and I'm sure people have done so; for example, SRFI-69 defines hash tables. But for now, let's see what we can do with the bare-bones approach.

Its usage is simple: you define a list of pairs, possibly augmenting them by consing new pairs onto it, or deleting elements from it. (The order doesn't really matter.) Then you use the aforementioned functions to look up "keys" (matched to the first element in each pair). If not found, #f is returned, otherwise the matching pair.

That's right; the whole pair is returned, not just the second element of the pair. By doing so, Scheme sidesteps the problem that some languages have (e.g. Ruby); it either returns a pair (found) or #f (not found), so there can never be any confusion whether the key was found or not. By contrast, in Ruby, if myhash[value] returns nil, that could mean that the value was found and that its associated value was nil, *or* that it was not found at all. (Python doesn't have this problem either; it raises a KeyError exception if the key is not found; in addition, the Ruby behavior can be emulated with the dict.get() method.)

Anyway, here's an example (R5RS only but we're secretly assuming that filter exists):

(define language-designers
  '((guido python)
    (matz ruby)
    (rasmus php)
    (larry perl)))

; add some...
(define language-designers
  (cons '(felix chicken) language-designers))

; I don't like PHP; remove it :-)
(define language-designers
  (filter (lambda (pair) (not (equal? (cadr pair) 'php)))
          language-designers))

(print (assoc 'guido language-designers))  ; => (guido python)
(print (assoc 'hans language-designers))   ; => #f

Note how the usage is completely different from Python's dicts. This can be written differently -- hell, OF COURSE it can be written differently, it's Scheme! :-) But let's stick with this approach for a minute.

(I'm using assoc here, which compares key and first element using the equal? predicate. assq and assv basically do the same thing, using the eq? and eqv? predicates, respectively. Equality testing in Scheme will be dealt with in yet another forthcoming post...)

Basically, this is all you need. Since a "dictionary" is just a list of pairs, all the usual list operators apply, and can be used to write any Python-esque dict operations fairly easily: keys, has_key, adding and removing using [], etc. (Doing so is left as an exercise for the reader. ;-)

Fortunately, the author of SRFI-1 (a list library) recognized the need for such functions, and supplied a few of them. Using the SRFI, we could write:

(define language-designers
  (alist-cons 'felix chicken language-designers))

(define language-designers
  (alist-delete 'rasmus language-designers))

... which is at least a bit clearer.

(More about Scheme lists, and SRFI-1 which is *very* necessary, in a separate post.)