Testing for proper lists
5th April 2019
I've been working on making my uLisp Lisp interpreter for microcontrollers handle improper lists correctly. Many introductions to Lisp make statements such as "The mapping functions mapc, mapcar, etc. must be followed by a function and one or more lists …", or "The append function must be followed by one or more lists". However, these statements aren't strictly true, because a dotted pair qualifies as a list:
> (listp '(2 . 3)) t
but this is an illegal argument to a mapping function:
> (mapc #'princ '(2 . 3)) 2 Error: 3 (of type FIXNUM) is not of type LIST.
Also, with append, it's more complicated. Only the last argument is allowed to end in a dotted pair:
> (append '(2) '(3) '(4 . 5)) (2 3 4 . 5))
A list that doesn't end in a dotted pair is called a proper list in the Common Lisp specification. Surprisingly there's no built-in function to test whether a list is a proper list or a list ending in a dotted pair.
Testing for a proper list
What's the easiest way to check for a proper list? We want to write a function properp which gives these results:
> (properp 2) nil
> (properp '(1 2 3)) t
> (properp '(1 2 . 3)) nil
At first sight it's not trivial, because we have to look all the way to the end of the list before we know whether it's a proper list.
A possible recursive definition is as follows:
(defun properp (l)
(cond ((null l) t)
((atom l) nil)
(t (properp (cdr l)))))
A simpler definition
The definition of a proper list is that it is a list whose last cdr is nil. So this leads to the following even simpler definition:
(defun properp (l) (null (cdr (last l))))
It's a bit more complicated
After writing the above I discovered that the following is perfectly valid:
> (mapcar #'list '(1 2 3) '(4 5 6 . 7)) ((1 4) (2 5) (3 6))
So it's not even true to say that "The mapping functions mapc, mapcar, etc must be followed by a function and one or more proper lists …".
blog comments powered by Disqus