Understanding function `tailp` in Common Lisp

The basic purpose of tailp is to check whether there is list structure shared. This means whether the cons cells are the same (which means EQL as a predicate) - not just the content of the cons cells.

One can also check if an item is in the last cdr:

CL-USER 87 > (tailp t '(1 2 3 4 . t))
T

CL-USER 88 > (tailp nil '(1 2 3 4 . nil))
T

CL-USER 89 > (tailp nil '(1 2 3 4))
T

CL-USER 90 > (tailp #1="e" '(1 2 3 4 . #1#))
T

This is one of the rarely used functions in Common Lisp.

Here is a case where tailp is useful:

(defun circular-list-p (l)
  (and (consp l)
       (tailp l (rest l))))

A couple of notes.

This terminates in all cases: tailp is allowed not to terminate on circular lists if the first argument is not a tail of the second (ie there's no requirement for it to check circularity), but it must terminate if the first argument is a tail of the second. But, if the list is circular, that's exactly what we check for here, so it terminates. (I was confused about this for a while).

The consp check is so (circular-list-p nil) is false: I think this is pragmatically the useful choice although you a pedant might argue that nil is circular.

I'm pretty sure the answer to (tailp '(3 4 5) '(1 2 3 4 5)) can be both t and nil as a smart compiler might do (tailp '#1=#(3 4 5) '(1 2 . #1#)) to reduce memory footprint. Quoted stuff are immutable literals so why not use the same memory twice?

Here is how tailp is working:

(defparameter *tail* (list 3 4 5))
(defparameter *larger* (list* 1 2 *tail*))
(defparameter *replica* (copy-list *larger*))

(tailp *tail* *replica*) ; ==> nil
(tailp *tail* *larger*)  ; ==> t

Since copy-list creates new cons for each element in a list it will share nothing but the empty list with any other list. It is unique.

*larger* has been made with a common tail with *tail* and thus (tailp *tail* *larger*) will be t.

It's important that it compares the arguments as same objects. Since the tail does not need to be a list it compares with eql. When comparing if stuff look the same you use equal so tailp is more specific than that. It has to be pointer equal (eq) or eql atomic value.

So where do you use this? I'm thinking a functional data structure where you typically reuse shared structure. tailp might be used to identify a subtree of a parent. It's basically a more performant version of this:

(defun my-tailp (needle haystack)
  (cond ((eql needle haystack) t)
        ((atom haystack) nil)
        (t (my-tailp needle (cdr haystack)))))