Lisp association list error

Question

I write the code that insert cons cell into association list. For example, there is association list

((1 . a) (3 . c) (4 . d))

and I want to insert cons cell (2 . b) then this program produces

((1  a) (2 . b) (3 . c) (4 . d))

but my code raises an exception

(car L) should be a lambda expression

below is my code

(defun INSERTCELL (R L)
  (cond ((< (car L) (car R)) cons((car L) INSERTCELL(R (cdr L))))
        (t cons(R L))))

R is (2 . b), and L is ((1 . a) (3 . c) (4 . d)) so R should be inserted into L.

Answer 1

Function calls in Lisp are cons cells:

(cons 1 2)
==> (1 . 2)

If you fix your code:

(defun insertcell (R L)
  (cond ((< (caar L) (car R)) (cons (car L) (insertcell R (cdr L))))
        (t (cons R L))))

it works:

(insertcell '(2 . b) '((1 . a) (3 . c) (4 . d)))
==> ((1 . A) (2 . B) (3 . C) (4 . D))

Note that you also need to do (caar L), not (car L) because L is an alist, so to access the first key you need to call car twice.

Answer 2

SDS's answer takes care of the typographical issue in your code, as well as some of the other bugs. That said, I think it's worth noting that there might be other ways to do this. First, association lists don't have to be stored in order. If you don't need yours to be in order, then you can simply use acons to add the new element to the beginning:

(let ((alist '((1 . a) (3 . c) (4 . d))))
  (acons 2 'b alist))
;=> ((2 . B) (1 . A) (3 . C) (4 . D))

If you do need to maintain the sorting condition, one option would be to use the approach above, and then sort the list afterward. That's probably a bit overkill, though, since you already know that the association list is sorted, and you only need to put the new element in its place. To that end, you can use the built in merge function to merge your association list and the new element (by wrapping it in a list, so it's a association list of one element):

(let ((alist (copy-list '((1 . a) (3 . c) (4 . d))))
      (new (list (cons 2 'b))))
  (merge 'list alist new '< :key 'car))
;=> ((1 . A) (2 . B) (3 . C) (4 . D))

or

(let ((alist '((1 . a) (3 . c) (4 . d))))
  (merge 'list (copy-list alist) (copy-list '((2 . b)))
         '< :key 'car))
;=> ((1 . A) (2 . B) (3 . C) (4 . D))

Note that merge is destructive (that is, it's allowed to modify its arguments), and that's why I used copy-list here to get fresh data. In your case, since you're probably building up the list incrementally, it's probably OK, as long as you save the result. E.g.,

(defun insert-cell (key value alist)
  (merge 'list alist (list (cons key value))
         '< :key 'car))

(let ((alist '()))
  (setf alist (insert-cell 1 'a alist))
  (setf alist (insert-cell 4 'd alist))
  (setf alist (insert-cell 3 'c alist))
  (setf alist (insert-cell 2 'b alist))
  alist)
;=> ((1 . A) (2 . B) (3 . C) (4 . D))