Why are conses sometimes lists and sometimes not?

Question

I thought I understood the basic elisp-structures: every list is a cons but not every cons is a list. Thus, if I do

(nth 1 '(a . b))

I get

(wrong-type-argument listp b)

but if I do

(nth 1 '(a b))

I get b. So I thought I'd use this for a function which recursively goes through a list and applies a function to every cons that is not a list. But now I find that I get t for

(listp '(a . b))

and indeed I, the documentation of listp says "Return t if OBJECT is a list, that is, a cons cell or nil.". So why are conses sometimes lists and sometimes not, and how can I test if a cons is a list under all definitions? I could use condition-case to test if elt is a cons but something like (nth 0 elt) gives an error, but isn't there something more elegant?

Answer 1

Conses only make a proper list when the car of the cons is a value and the cdr is another proper list. This means that in a proper list, the final cdr must end up being nil. Thus '(a . (b . (c . nil))) is a proper list, while '(a . (b . c)) is not. Since writing lists is extremely common but writing them as conses is so cumbersome, the lisp reader lets us type in '(a b c) instead. The reader expands it to '(a . (b . (c . nil))) for us.

Yes, the term “list structure” is often used for any sort of data structure even when it isn’t a proper list. However, that is merely because we humans are lazy and “cons structure” is a lot harder to say.

Don’t feel that you are required to use proper lists and only proper lists, however. It is perfectly fine to cons things up however you like. Just be aware that you won’t be able to use nth to access the elements. For example, suppose you wanted to store complex numbers and rational numbers as conses. You could do something like this:

(defun complex (a b)
  (cons 'complex (cons a b)))
(defalias real cadr)
(defalias imag cddr)
(defun +complex (z1 z2)
  (complex (+ (real z1) (real z2))
           (+ (imag z1) (imag z2))))

(defun rational (n d)
  (cons 'rational (cons n d)))
(defalias numer cadr)
(defalias denom cddr)
(defun +rat (a b)
  (rational (+ (* (numer a) (denom b))
               (* (denom a) (numer b)))
            (* (denom a) (denom b))))

And so on. You can see that the accessor functions real and imag for complex numbers and numer and denom for rational numbers are written using car and cdr (or rather cadr and cddr) instead of nth. (Of course production‐quality code would be more careful about checking the type tags!)

Answer 2

I found the right function: proper-list-p. Apparently there is a difference between lists and "proper lists". The elisp manual says "Because most cons cells are used as part of lists, we refer to any structure made out of cons cells as a “list structure”." I find that a bit confusing, but fine.