Michael J. Forster
L-99: P01 - Find the last box of a list.

MY-LAST is a special case of the Common Lisp (CL) LAST function: it accepts a list, which might be a dotted list but must not be a circular list; and returns a cons, not an element.

Thus MY-LAST must handle lists terminated by either the empty list or some other atom (CLHS 14.1.2). For example,

(my-last 42) ; TYPE-ERROR
(my-last nil) =>  NIL
(my-last '(1 2 3)) =>  (3)
(my-last '(1 2 . 3)) =>  (2 . 3)

List traversal lends itself to a recursive definition. Experience with languages like Scheme, Clojure, and Haskell might suggest the following:

(defun my-last-bad (l)
  (cond
    ((null l) nil)
    ((null (cdr l)) l)
    (t (my-last-bad (cdr l)))))

However, as noted above, in CL, a list need not be terminated by the empty list. MY-LAST-BAD will fail, eventually, on a dotted list:

CL-USER> (trace my-last-bad)
(MY-LAST-BAD)
CL-USER> L-99> (my-last-bad '(1 2 . 3))
  0: (MY-LAST-BAD (1 2 . 3))
    1: (MY-LAST-BAD (2 . 3))
      2: (MY-LAST-BAD 3)
; Evaluation aborted on #<TYPE-ERROR expected-type: LIST datum: 3>.

The problem is that CDR expects either a cons or the empty list. When passed an atom other than the empty list (the terminating atom of a dotted list, for instance) CDR signals an error.

The real problem, however, is the use of NULL. (And, no, using ENDP instead would not solve the problem. The purpose of ENDP, as the HyperSpec says, “is to test for the end of proper list.” MY-LAST must handle dotted as well as proper lists.)

As Erik Naggum said,

A much more robust way is not to test for the end of the list at all, but to test for a cons cell that would require more traversal.

It is sloppy to pass anything non-‘nil’ to ‘cdr’; careful programming demands that you know that you pass ‘cdr’ a cons cell.

The following version does just that and works as advertised:

(defun my-last (l)
  (check-type l list)
  (if (and (consp l) (consp (cdr l)))
      (my-last (cdr l))
      l))

Although most CL implementations offer tail-call optimization, the CL standard does not guarantee it. Some would prefer an iterative definition, similar to the example from the HyperSpec:

(defun clhs-last (list)
   (do ((l list (cdr l))
        (r list)
        (i 0 (+ i 1)))
       ((atom l) r)
     (if (>= i 1) (pop r))))

Still, MY-LAST does run faster and conses less than CLHS-LAST under SBCL 1.0.50 on my machine, although both pale in comparison to LAST:

CL-USER> (compile 'my-last)
=> MY-LAST

CL-USER> (compile 'clhs-last)
=> CLHS-LAST

CL-USER> (setf *list* (loop for i below 1000000 collect i))
=> ...

CL-USER> (time (dotimes (i 1000) (my-last *list*)))

Evaluation took:
  4.985 seconds of real time
  4.983243 seconds of total run time (4.983243 user, 0.000000 system)
  99.96% CPU
  9,944,179,717 processor cycles
  41,792 bytes consed
=> NIL

CL-USER> (time (dotimes (i 1000) (clhs-last *list*)))

Evaluation took:
  10.141 seconds of real time
  10.136459 seconds of total run time (10.136459 user, 0.000000 system)
  99.95% CPU
  20,230,882,215 processor cycles
  67,464 bytes consed
=> NIL

CL-USER> (time (dotimes (i 1000) (last *list*)))

Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  5,828 processor cycles
  0 bytes consed
=> NIL