Searching an Association List

In my previous post I described an association list as a list of two element lists as ((x1 y1) (x2 y2) ... (xn yn)). However, the real purpose of an association list, as the name suggests is to associate one element with another. Thus, an association list denotes a list of key value pairs as ((k1 v1) (k2 v2) ... (kn vn)) where all the ki's refer to the value of the key while the vi's denote the value associated with ki. The keys must be distinct as the presence of duplicate keys would either mean that a key-value pair has been repeated or a key is associated with multiple values which defeats the purpose of an association list.

In this post, I review the assoc. function that takes as input a key x and an association list, y, and returns the value associated with the key. The function actually returns the second element of the first two element list in y whose first element is x.

The code for the assoc. function :

    (defun assoc. (x y)
        (cond ((eq (caar y) x) (cadar y))
               ('t  (assoc. x (cdr y)))))

As you can see the function is pretty short and simple. The element x is the key that has to be searched for in the association list y. Once again, we have the cond form. And once again, as found in the functions subst1,append. and pair. the cond form contains two parts. The simple base case and the second inductive case.

Consider the following examples where the first part of the cond form, the simple base case, is satisfied,

    (setq alphabets   '((1 a) (2 b) (3 c)))
    (setq companies   '((search google) (lisp ITA) (databases oracle)))   
    (setq favourites  '((sport cricket) (distro ubuntu) (editor emacs)))

    (assoc. '1 alphabets)          ==> a
    (assoc. 'search companies)     ==> google
    (assoc. 'sport  favourites)    ==> cricket

In all three examples above, the key was found to be equal to the first element of the very first two element list. For instance if you consider the first example,

    (car alphabets)           ==> (1 a)

And hence

    (eq (caar alphabets) '1)  ==> t

    ;; The returned value was 
    (cadar alphabets)    ==> a

The inductive step for the assoc. function is the simplest of inductive cases seen so far. If the first element of the first list is not equal to the key value, then, we repeat the search on the rest of the association list using (cdr y).

Let's trace the execution of the program on the example below,

    (assoc. 'editor favourites)

                            (assoc. 'editor favourites)

                                         ||
                                         ||
                                         \/


                (assoc. 'editor '((sport cricket) (distro ubuntu) (editor emacs)))

                                         ||
                                         ||
                                         \/

                (assoc. 'editor (cdr '((sport cricket) (distro ubuntu) (editor emacs))))

                                         ||
                                         ||
                                         \/

                       (assoc. 'editor '((distro ubuntu) (editor emacs)))

                                         ||
                                         ||
                                         \/
                
                       (assoc. 'editor (cdr '((distro ubuntu) (editor emacs))))

                                         ||
                                         ||
                                         \/
                
                          (assoc. 'editor '((editor emacs)))

                                         ||
                                         ||
                                         \/
                
                              (cadar '((editor emacs)))        

                                         ||
                                         ||
                                         \/
                
                                       emacs

However, there is a problem with the function assoc. as described above. The bug appears when you try to search the association list for a key that is not present in the list. Ideally, the assoc. function must return nil. However, it does not.

    (assoc. 'os favourites)

Can you modify the assoc. function to avoid the above error and make the assoc. function return nil?