28 Aug 09 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
"http://linuxandlisp.blogspot.com/2009/08/in-next-few-posts-i-intend-to-go-over.html"
target="_blank">subst1,
target="_blank">append. and
target="_blank">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?
