Defining setf behavior (Or is there an easier way?)

So, I notice I frequently type

(cdr (assoc key list))

in my code to access the values of associative lists.

First, I'm surprised I haven't been able to find an easier way to do this. Surely accessing a value from an associative array is not a rare task. Am I missing something?

What I've ended up doing is making it into a function:

(defun cadsoc (key lis) (cdr (assoc key lis)))

The problem with this is that I can't alter the value. If I use (cdr (assoc)) I can setf it to whatever I want, but setf doesn't know what to do with my function. How do I teach it?

Just learning myself, but might a hash table do what you want?

You can make them with:

(defparameter *hash-table* (make-hash-table))

Create new entries with:

(setf (gethash 'entry-key *hash-table*) value)

And fetch them back with:

(gethash 'entry-key *hash-table*)

Which will return the associated value and true if it's found, or NIL and false otherwise.

Using GETHASH does not change the basic issue.

The easy solution is to use a SEFT definition

(defun (setf cadsoc) (v key alist)
   (let ((kv (assoc key alist)))
      (if kv (setf (cdr kv) v) (error "Key ~S not found in a-list." key))))

Now you can do:

CL-USER 2 > (defvar l (acons 42 'a ()))
L

CL-USER 3 > al
((42 . A))

CL-USER 4 > (setf (cadsoc 42 al) 'qwerty)

CL-USER 4> al
((42 . QWERTY))

Once you have grokked SETF functions (and DEFSETF) you can move on to using hash tables, which, indeed may be better for your needs.

Cheers
--
MA

Thanks, I actually already figured it out in the time it took for the original post to be approved.

(defun cadsoc (key lis) (cdr (assoc key lis)))

(defun (setf cadsoc) (value key lis) (if (assoc key lis) (setf (cdr (assoc key lis)) value) (setf (cdr (last lis)) (cons (cons key value) ()))))

The great thing about this is if the key does not exist, the setf will create it.

As for hash tables, I considered it, but I thought I read somewhere that they're less efficient than associative arrays unless you have thousands of keys or something like that. Was I misinformed?

Sure.

BTW. Your version behaves more like (SETF GETHASH). It's a design choice.

MA

What is that "sure" in response to? Sure hash tables are less efficient, or sure I was misinformed?

The real efficiency difference between association lists and hash-tables is implementation dependent, but as a rule of thumb you can say that association lists are ok for a number of up to ten key/value pairs. If you have more pairs then hash-tables usually are faster. Common Lisp provides the TIME macro where you can test yourself which one is better for your program.

- edgar

I see, thanks. I thought it was a much bigger number than ten. Even so, most of what I use alists for is smaller.

Just tested: with SBCL 1.1.13 on Debian 7.1 Wheezy (Linux) a ten-pairs hash-table is double as fast as a ten-pairs a-list. This is not for nit-picking, I only wanted to know how much the difference really is.

First I define a list of all keys:

CL-USER> (defparameter *keys* '(a b c d e f g h i j))
*KEYS*

Then I define an association list containing all keys and some fixnum values:

CL-USER> (defparameter *a-list*
           '((a . 0) (b . 1) (c . 2) (d . 3) (e . 4)
             (f . 5) (g . 6) (h . 7) (i . 8) (j . 9)))
*A-LIST*

Here I test if ASSOC finds all values:

CL-USER> (mapcar (lambda (x) (cdr (assoc x *a-list*))) *keys*)
(0 1 2 3 4 5 6 7 8 9)

Now I run the test one million times on the *a-list*. I'm using MAPC instead of MAPCAR because MAPC doesn't need to allocate memory for the resulting list (= 0 bytes consed), so the result later can be compared with the hash-table result.

CL-USER> (time (dotimes (n 1000000)
                 (mapc (lambda (x) (cdr (assoc x *a-list*))) *keys*)))
Evaluation took:
  1.239 seconds of real time
  1.240078 seconds of total run time (1.240078 user, 0.000000 system)
  100.08% CPU
  2,449,594,250 processor cycles
  0 bytes consed
NIL

I make a hash-table and copy the key/value pairs from the association list into the hash-table:

CL-USER> (defparameter *h-table* (make-hash-table :size 10))

CL-USER> (mapcar (lambda (x)
                   (setf (gethash (car x) *h-table*) (cdr x)))
                 *a-list*)
(0 1 2 3 4 5 6 7 8 9)

I test if GETHASH finds all values:

CL-USER> (mapcar (lambda (x) (gethash x *h-table*)) *keys*)
(0 1 2 3 4 5 6 7 8 9)

Now I run the test one million times on the hash-table:

CL-USER> (time (dotimes (n 1000000)
                 (mapc (lambda (x) (gethash x *h-table*)) *keys*)))
Evaluation took:
  0.622 seconds of real time
  0.628039 seconds of total run time (0.628039 user, 0.000000 system)
  100.96% CPU
  1,303,777,083 processor cycles
  0 bytes consed

Result:

• Association list: 1.239 seconds
• Hash-table: 0.622 seconds

This may be different with other Common Lisp implementations, so you can use the code above and run it with your implementation.

- edgar

I see, thanks for your help.