logo标签列表

理解Common Lisp中的函数`tailp`

lispcommon-lispsbclclisp
6

我在阅读 Bert Burgemeister 的“Common Lisp Quick Reference”时，发现了tailp。

起初，我对这个函数的定义产生了误解。然后我尝试了：

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

但是它返回了。
NIL

CLTL2中说，tailp为真当且仅当第一个参数是任意一个带有现有索引n的(nthcdr n list)。
(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...有点像..."给定列表的任何cdr导数等于第一个参数？"
但也许有人可以解释一下在哪些情况下这种测试非常有用？
备注：
在与@Lassi的长时间讨论中here，我们发现：
永远不要在循环列表上使用tailp！
因为行为未定义（在SBCL中已经有问题）。所以tailp适用于非循环列表。
1
当超级规范(hyperspec)表示某些事物是“相同”的时候，但没有提及在什么测试下，“EQL”是默认值。“TAILP”似乎不是特别有用的测试。我安装的quicklisp dists快速搜索显示cl-yacc是唯一的用户。从代码的快速浏览中，它似乎从相同的列表(语法优先级)中获取两个cons单元(OP1-TAIL和OP2-TAIL)，并使用TAILP检查OP2-TAIL是否是OP1-TAIL的cdr的尾部，这意味着OP1在优先级列表中排名第一。 - jkiiski
1
谢谢你，@jkliski！啊，我应该想到在我拥有的Lisp源代码中使用grep来查找它！-感谢您的提示-在Lisp的解释和定义中，“same”==“EQL”。好吧... TAILP可以作为列表内优先级/后继测试...由于它直接查看位置，因此可能比其他构造的测试更有效，不是吗？ - Gwang-Jin Kim
4个回答
6
tailp 的基本目的是检查是否存在共享的列表结构，这意味着 cons 单元格 是否相同（这意味着使用 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中很少用到的函数之一。
其实我一开始也试过使用数字和符号。但这有点误导人。因为它只能在你的例子中工作，因为 nil、t 和所有数字以及所有符号都根据定义只有一个物理表示/地址。例如，(tailp "e" '("a" "b" "c" "d" . "e")) 返回 NIL。 - Gwang-Jin Kim
1
@Gwang-Jin Kim：不，相同的数字值可以有多个对象。对于数字，测试EQ可能为false，而EQL可能为true。默认的sameness断言是EQL，它将数字和字符视为特殊情况。如果“e”实际上是相同的对象，则您的示例可以正常工作。 - Rainer Joswig
是的，真的...我曾经为自己制作了一个相等性列表 ;; 相同符号？（共享相同地址？）eq ;; 相同类型和相同大小写字符/数字？eql ;; 相同数字（数学意义上，类型不敏感）= ;; 相同大小写字符串，相等对象列表（vec / obj eq！）equal ;; 相同对象（也包括向量），不区分大小写的字符串equalp-使用equal时，字符串开始变得“相同”。 - Gwang-Jin Kim
哦，这是什么样的符号表示法。我在创建循环列表时看到了它。这是一种地址引用，不是吗？ - Gwang-Jin Kim
1
@Gwang-JinKim：这用于读取和打印S表达式，其中对象在结构中共享。请参见：*print-circle*。 - Rainer Joswig
1
谢谢！- 我想现在我们已经理解了tailp ;) 。感谢您的贡献！ - Gwang-Jin Kim
4
这里有一个使用tailp的案例，它非常有用：
(defun circular-list-p (l)
  (and (consp l)
       (tailp l (rest l))))

一些注意事项。
在所有情况下，这都会终止：如果第一个参数不是第二个参数的尾巴（即没有要求检查循环），则允许tailp在循环列表上不终止，但如果第一个参数是第二个参数的尾巴，则必须终止。但是，如果列表是循环的，那么这正是我们在这里检查的，所以它会终止。（我曾经对此感到困惑） consp检查以使(circular-list-p nil)为false：我认为这是实用的选择，尽管有些人可能会争辩说nil是循环的。
1
如果 l 在一个或多个初始元素之后有循环子列表，则此方法将无法正常工作。例如 (circular-list-p (list* 1 2 3 (let ((sub (list 4 5 6))) (setf (cdr (last sub)) sub))))。 - Lassi
关于循环列表的tailp的详细探讨：https://dev59.com/67noa4cB1Zd3GeqPNkiJ#60253743 - Lassi
1
“循环尾”是一个不错的术语。在Common Lisp中，任何带有循环尾的列表都被认为是循环的：“循环列表n.一系列cons没有终止，因为链中的某些cons是后面cons的cdr。”我不知道这是否是更广泛的标准定义，但它可能是最有用的定义。是否有一个应用程序只需要检测特定的循环而不是其他循环？ - Lassi
1
你可以使用函数 (length-cycle xs) => length-of-non-repeating-part; length-of-repeating-part 来处理前两种情况。这可能适用于标准库。在列表中，只能通过算法检测到一个循环，因为在遍历过程中算法会陷入该循环中。第三种情况需要遍历某些 conses 的 car，因此不清楚如何在标准库函数中实现它。 - Lassi
1
@Lassi：我需要再考虑一下这个问题（SE评论不是讨论它的正确场所，因为它们会被修剪），但我认为我已经说服自己了，因为cons的cdr最多只能指向一个对象，所以将列表视为cdr链（忽略car），最多只能有一个循环：当您沿着conses走时，每个cdr都指向不是cons的某些东西，指向新的cons或指向其自身历史中的cons。 - user5920214
显示剩余3条评论
3
我很确定对于`(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为列表中的每个元素创建新的cons，因此它与任何其他列表共享的仅是空列表。它是独一无二的。

*larger*已经与*tail*具有公共尾部，因此(tailp *tail* *larger*)将是t。

重要的是将参数视为相同对象进行比较。由于尾部不需要是列表，因此它与eql进行比较。当比较是否类似时，使用equal，因此tailp比这更加特定。它必须是指针相等(eq)或者eql原子值。

那么你在哪里使用它呢？我想到了一个函数式数据结构，在这种数据结构中，您通常会重用共享结构。 tailp可能用于识别父级的子树。基本上，它是这种操作的更高效版本：

(defun my-tailp (needle haystack)
  (cond ((eql needle haystack) t)
        ((atom haystack) nil)
        (t (my-tailp needle (cdr haystack)))))
谢谢你，@Sylwester！我已经添加了更长的回答作为新的回答！（在下面或上面...）;) - Gwang-Jin Kim
2

@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将是一个非常有用的测试...
  • 或者像你说的那样，如果实现使用尾巴摇动来提高性能（并可能不断跟踪列表的尾巴），在这种情况下，实现可以使用tailp作为测试，以确定给定的列表是否作为最近添加的尾巴对另一个列表产生贡献...

当我阅读您的回答时，这刚刚浮现在我的脑海中，@Sylwester！（我没有意识到这一点，当我在书中阅读关于尾巴摇动的内容时 - （顺便说一句，这是一本非常有用的书！）谢谢您的回答！

2
队列可以像这样实现，例如在http://norvig.com/paip/auxfns.lisp中的小*Queues*部分。 - coredump
感谢@coredump提供的好链接！我现在也在Edi Weitz的书中看到他提到了tailp，用于完全这样的目的...他推荐使用ldiff来提取列表(ldiff *list* *tail*)中的非公共部分，该部分是list和tail之间的不同部分。我应该先在他和Norvig的书中搜索:D。 - Gwang-Jin Kim
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接