理解 Common Lisp 中的函数 `tailp`

Question

在浏览 Bert Burgemeister 的 "Common Lisp Quick Reference" 时，我偶然发现了 tailp。

首先，我误解了这个函数的定义。我试过了：

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

但是它返回了

NIL

CLTL2 说，tailp 是真的 iff 第一个参数是任何 (nthcdr n list) 和现有的 n.

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

我进一步尝试：

(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

直到我尝试（然后理解 tailp 寻找 l 的 cdr 甚至共享相同的地址）：

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

但是我有下一个问题：

For what such a function is useful at all?

检查子列表是否是列表的一部分的函数不是更有用吗？（或者 看起来像 列表的一部分，而不是它必须共享相同的地址？）

备注：

啊，好吧，慢慢地我开始明白，也许这是列表的 cdr 部分的 eq ……有点……"Any cdr-derivative of given list eq to the first argument?"。

但是也许有人可以向我解释一下这种测试在哪些情况下非常有用？

备注：

在与@Lassi 的长时间讨论中，我们发现：

永远不要在循环列表中使用 tailp！

因为行为未定义（在 SBCL 中已经有问题）。所以 tailp 用于非循环列表。

Answer 1

tailp的基本目的是检查是否有共享列表结构。这意味着 cons cells 是否相同（这意味着 EQL 作为谓词）——而不仅仅是 cons cells 的内容。

还可以检查某项是否在最后 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

这是 Common Lisp 中很少使用的函数之一。

Answer 2

我很确定 (tailp '(3 4 5) '(1 2 3 4 5)) 的答案可以是 t 和 nil，因为智能编译器可能会 (tailp '#1=#(3 4 5) '(1 2 . #1#)) 来减少内存占用。引用的东西是不可变的文字，所以为什么不使用相同的内存两次？

以下是 tailp 的工作方式：

(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

由于 copy-list 为列表中的每个元素创建新的缺点，它将共享除了带有任何其他列表的空列表之外什么都没有。独一无二。

*larger* 与 *tail* 有一个共同的尾巴，因此 (tailp *tail* *larger*) 将是 t.

重要的是它将参数比较为相同 objects。由于尾部不需要是列表，因此它与 eql 进行比较。当比较东西看起来是否相同时，你使用 equal 所以 tailp 比那更具体。它必须是指针等于 (eq) 或 eql 原子值。

所以你在哪里使用它？我正在考虑一个功能数据结构，您通常会在其中重用共享结构。 tailp 可用于标识 parent 的子树。它基本上是一个性能更高的版本：

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

Answer 3

@Sylwester：

谢谢@Sylwester！

我最近在 Edi Weitz 的书中读到关于摇尾巴列表的内容：

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

这会将列表最后一个 cons 单元格的汽车命名为 *tail* - 现在，可以向其中添加一个新元素并重命名列表最后一个 cons 单元格的新最后一辆车 *tail*。

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

现在的列表是：

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

并且可以通过 setf 添加更多内容到 *tail*，而无需再次遍历列表。（因此提高了性能。但当然会有警告，因为这是一种破坏性操作）。

也许，如果有人像你一样命名一个列表：

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

和tail wagg它到新列表的末尾

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

啊或者：

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

然后

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

将是测试，这个过程是否正确完成
也将是一个测试，除了 *my-new-tail* 之外我是否添加了一条新尾巴，或者 *my-new-tail* 是否是最后一个尾巴摇到 *list* 或不...
因此 tailp 在摇尾巴的情况下将是一个非常有用的测试 ...
或者像你说的那样，如果一个实现出于性能原因使用 then tail wagging，（并且可能不断跟踪列表的尾部）在这种情况下，该实现可以使用 tailp 作为测试给定列表是否作为最近添加的尾巴对另一个列表做出贡献...

这是我在阅读您的回答时想到的，@Sylwester！（我在书中读到关于摇尾巴的时候没有意识到这一点 - （顺便说一下，这是一个超级有用的！）谢谢你的回答！

Answer 4

这里是 tailp 有用的例子：

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

一些笔记。

这在所有情况下都会终止：如果第一个参数不是第二个参数的尾部（即不需要检查循环性），则允许 tailp 在循环列表上不终止，但它必须如果第一个参数是第二个参数的尾巴则终止。但是，如果列表是循环的，这正是我们在这里检查的内容，因此它会终止。（我有一段时间对此感到困惑）。

consp 检查结果 (circular-list-p nil) 为假：我认为这在实用上是有用的选择，尽管你这个学究可能会争辩说 nil 是循环的。

理解 Common Lisp 中的函数 `tailp`

Understanding function `tailp` in Common Lisp

lisp

clisp

sbcl

common-lisp

备注：