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

Discussion of Common Lisp
Post Reply
Gopher
Posts: 18
Joined: Mon Nov 25, 2013 1:01 am

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

Post by Gopher » Mon Nov 25, 2013 8:14 pm

So, I notice I frequently type

Code: Select all

(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:

Code: Select all

(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?

Cass
Posts: 6
Joined: Thu Oct 24, 2013 8:14 am

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

Post by Cass » Thu Nov 28, 2013 12:44 pm

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.

marcoxa
Posts: 85
Joined: Thu Aug 14, 2008 6:31 pm

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

Post by marcoxa » Thu Nov 28, 2013 2:57 pm

Using GETHASH does not change the basic issue.

The easy solution is to use a SEFT definition

Code: Select all

(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:

Code: Select all

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
Marco Antoniotti

Gopher
Posts: 18
Joined: Mon Nov 25, 2013 1:01 am

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

Post by Gopher » Thu Nov 28, 2013 5:11 pm

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

Code: Select all

(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?

marcoxa
Posts: 85
Joined: Thu Aug 14, 2008 6:31 pm

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

Post by marcoxa » Fri Nov 29, 2013 12:48 am

Sure.

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

MA
Marco Antoniotti

Gopher
Posts: 18
Joined: Mon Nov 25, 2013 1:01 am

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

Post by Gopher » Sat Nov 30, 2013 12:08 am

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

edgar-rft
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

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

Post by edgar-rft » Sat Nov 30, 2013 4:39 am

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

Gopher
Posts: 18
Joined: Mon Nov 25, 2013 1:01 am

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

Post by Gopher » Sat Nov 30, 2013 5:43 am

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

edgar-rft
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

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

Post by edgar-rft » Sat Nov 30, 2013 5:24 pm

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:

Code: Select all

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:

Code: Select all

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:

Code: Select all

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.

Code: Select all

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:

Code: Select all

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:

Code: Select all

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:

Code: Select all

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

Gopher
Posts: 18
Joined: Mon Nov 25, 2013 1:01 am

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

Post by Gopher » Sun Dec 01, 2013 12:20 am

I see, thanks for your help.

Post Reply