代码之家 › 专栏 › 技术社区 › Gwang-Jin Kim

理解Common Lisp中的函数“tailp”

clisp sbcl common-lisp lisp

6

Gwang-Jin Kim · 技术社区 · 6 年前

在浏览伯特·伯格梅斯特的《公共口齿不清快速参考》时,我绊倒了 tailp .

首先,我误解了这个函数的定义。我试着:

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

但它回来了

NIL

CLTL2说, 尾巴 这是真的 敌我识别 第一个论点是 (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

直到我尝试(然后理解) 尾巴 寻找 cdr 属于 l 共享同一地址):

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

但后来我有了下一个问题:

For what such a function is useful at all?

查看子列表是否是列表的一部分不是一个更有用的函数吗?(或 看起来像 列表的一部分,而是必须共享同一地址?)

备注:

啊,好吧,慢慢地我开始明白,也许这是一种 eq 对于 cdr 列表的一部分。。。有点“有吗 cdr -给定列表的导数 情商 第一个论点?".

但也许有人能告诉我在什么情况下这样的测试是非常有用的?

备注:

在与@Lassi的长时间讨论中 here ,我们发现:

永远不要使用 尾巴 在传单上!

因为行为未定义(在SBCL中已经存在问题)。所以 尾巴 用于非循环列表。

4 回复 | 直到 5 年前

1

6

Rainer Joswig mmmmmm 6 年前

基本目的 tailp 检查是否有共享的列表结构。这意味着 地址对 都一样(意思是 EQL 作为谓词),而不仅仅是cons单元格的内容。

你也可以检查一个项目是否在最后一个 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中很少使用的函数之一。

2

4

user5920214 user5920214 6 年前

这里有一个例子 tailp 是有用的:

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

几张便条。

这在所有情况下都会终止: 尾巴 如果第一个参数不是第二个参数的尾部(即不要求它检查循环性),则不允许在循环列表上终止,但如果第一个参数是第二条尾巴。但是,如果列表是循环的,这正是我们在这里检查的内容,因此它终止。(我对此困惑了一段时间)。

这个 consp 支票就是这样 (circular-list-p nil) 这是错误的:我认为这是一个实用的选择,尽管你是一个学究,可能会说: nil 它是圆形的。

3

Sylwester 6 年前

我很确定这个问题的答案 (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 为它将共享的列表中的每个元素创建新的CON 只有空列表和其他列表。它是独一无二的。

*larger* 是用一条普通的尾巴做成的 *tail* 因此 (tailp *tail* *larger*) 将 T .

重要的是,它将参数作为相同的对象进行比较。因为尾部不需要是一个列表,它可以与之进行比较 eql .当比较物品是否与你使用的相同时 equal 所以 尾巴 比这更具体。它必须是指针相等的( eq )或者 eql 原子值。

你在哪里用这个?我在考虑一种功能性数据结构,在这种结构中,您通常会重用共享结构。 尾巴 可能用于标识父级的子树。基本上,这个版本是:

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

4

2

Gwang-Jin Kim 6 年前

@西尔维斯特:

谢谢你,@sylvester!

我最近在Edi Weitz的书中读到了关于摇尾巴的列表:

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

这将列表中最后一个cons单元的汽车命名为 *tail* -现在,我们可以添加一个新元素,并将列表中最后一个cons单元格中的新最后一辆车重命名 *尾巴* .

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

现在的清单是:

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

你可以通过 setf 进一步的事情 *尾巴* 无需再次浏览列表。(这样可以提高性能。但当然需要警告,因为这是一种破坏性的行为)。

也许,如果有人能像你一样列出一份清单:

(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* 或者不,或者如果 *我的新尾巴* 这是最后一条被摇尾巴的尾巴 *list* 或者不是。。。
因此 tailp 在摇摆尾巴的情况下会是一个非常有用的测试。。。
或者像您所说的,如果一个实现出于性能原因而使用then tail WANGING(并且可能不断跟踪列表的尾部),那么在这种情况下,该实现可以使用 尾巴 作为一个测试,一个给定的列表是否会像最近添加的尾部一样贡献给另一个列表。。。

当我读到你的答案时,我突然想到了这一点,@sylvester!(我在书中读到关于摇尾巴的内容时没有意识到这一点(顺便说一句,这是一个非常有用的东西!)谢谢你的回答!