Understanding tailp in Common Lisp

问题:

While looking through the "Common Lisp Quick Reference" by Bert Burgemeister, I stumbled over tailp.

First, I misunderstood the definitions of this function. And I tried:

(tailp '(3 4 5) '(1 2 3 4 5))

But it returned

NIL

CLTL2 says, tailp is true iff the first argument is any (nthcdr n list) with existing n.

(nthcdr 2 '(1 2 3 4 5))
;; (3 4 5)

I further tried:

(tailp '(3 4 5) '(1 2 3 4 5))
;; NIL - and I would expect: T following the definition above.

(tailp '() '(1 2 3 4 5))
;; T
(tailp '5  '(1 2 3 4 . 5))
;; T

Until I tried (and then understood tailp looks for cdr of l which share even the same adress.

(defparameter l '(1 2 3 4 5 6))
(tailp (nthcdr 3 l) l)
;; T

But then I had my next question:

For what such a function is useful at all?

Wouldn't be a function more useful which looks whether a sublist is part of alist? (Or looks like a part of a list, instead that it has to share the same address?)

Remark:

Ah okay slowly I begin to understand, that maybe that this is kind of a eq for cdr parts of a list ... Kind of ... "Any cdr-derivative of given list eq to to the first argument?".

But maybe someone can explain me in which situations such test is very useful?

回答1:

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.

回答2:

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)))))

回答3:

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.

回答4:

@Sylwester:

Thank you, @Sylwester!

I recently read in Edi Weitz's book about tail wagging a list:

(defparameter *list* (list 'a 'b 'c 'd))
(defparameter *tail* (cdddr *list*))

This names the car of the last cons cell of the list as *tail* - and now, one can add to it a new element and rename the new last car of the last cons cell of the list *tail*.

(setf (cdr *tail*) (cons 'e 'nil) 
      *tail*       (cdr *tail*)) 
;; (E)

Now the list is:

*list* 
;; (A B C D E) 

and one can add via setf further things to *tail* without having to traverse the list again. (So improves performance. But with a warning of course, because this is a destructive action).

Perhaps, if one would name a list like you did:

(defparameter *my-new-tail* '(F G H))

and tail wagg it to the end of the new list

(setf (cdr *tail*) *my-new-tail*
      *tail* (cddr *my-new-tail*))

Ah or alternatively:

(defparameter *tail-of-my-new-tail* (cddr *my-new-tail*))
;; and then
(setf (cdr *tail*) *my-new-tail*
      *tail*       *tail-of-my-new-tail*)

Then

(tailp *my-new-tail* *list*)

• would be the test, whether this procedure was done correctly
• would also be a test, whether I added a new tail in addition to *my-new-tail* or not or if *my-new-tail* was the last tail which has been tail wagged to *list* or not ...
• therefore tailp would be a quite useful test in the context of tail wagging ...
• or like you said, if an implementation uses then tail wagging for performance reasons, (and perhaps keeping track of the tails of the lists constantly) in this context, the implementation could use tailp as a test whether a given list contributes to another list as the recently added tail ...

This just came into my thoughts, when reading your answer, @Sylwester! (I didn't realize this while reading about tail wagging in the book - (which is by the way a super useful one!) Thank you that you answered!