检查 lisp 中的循环性 - 通过递归函数相同的变量

Question

我正在尝试创建一个函数来测试给定列表是否是循环的，重新起点是列表的开头。

预期结果：

(setq liste '(a b c))
(rplacd (cddr liste) liste)

(circular liste) => t
(circular '(a b c a b c)) => nil

因为我只是想测试是否有任何后续项目是第一个 'eq'，所以我不想构建整个 tortoise and hare algorithm。

这是我的代码：

(defun circular (liste)
    (let (beginningliste (car liste)))
    (labels ( (circ2 (liste)
      (cond
        ((atom liste) nil)
        ((eq (car liste) beginningliste) t)
        (t (circ2 (cdr liste)))
        ) ) ) ) )

它没有给出预期的结果，但我不明白我的错误在哪里
我不确定我是否正确使用 'labels'
有没有不用 'labels' 的方法？

编辑。我想我已经回答了我的第三个问题，因为我认为我找到了一种更简单的方法。这行得通吗？

(defun circular (liste)
   (cond
      ((atom liste) nil)
      ((eq (car liste) (cadr liste)) t)
      (t  (circular (rplacd liste  (cddr liste))))
      )
   )

Answer 1

首先，当您改变常量数据时，行为是未定义的：当您引用某物（此处为列表）时，Lisp 环境有权将其视为常量。另见 this question 为什么 defparameter 或 defvar 优于 setq。所以...

(setq list '(a b c))
(rplacd (cddr list) list)

...最好写成：

(defparameter *list* (copy-list '(a b c)))
(setf (cdr (last *list*)) *list*)

其次，您的代码格式错误且命名约定不正确（请使用破折号分隔单词）；这是在 emacs 的帮助下使用常规布局：

(defun circularp (list)
  (let (first (car list)))
  (labels ((circ2 (list)
             (cond
               ((atom list) nil)
               ((eq (car list) first) t)
               (t (circ2 (cdr list))))))))

使用这种格式，有两件事应该很明显：

let不包含体形式：您定义局部变量并且从不使用它们；您也可以删除 let 行。
此外，let 缺少一对括号：您编写的内容定义了一个变量名称 first 和另一个名为 car 的变量，绑定到 list。我假设您想将 first 定义为 (car list).
您定义了一个本地 circ2 函数，但从未使用过它。我希望 circularp 函数（-p 用于 "predicate"，如 numberp、stringp）调用 (circ2 (cdr list))。我更喜欢将 circ2 重命名为 visit（或 recurse），因为它意味着什么。

通过上述更正，即：

(defun circularp (list)
  (let ((first (car list)))
    (labels ((visit (list)
               (cond
                 ((atom list) nil)
                 ((eq (car list) first) t)
                 (t (visit (cdr list))))))
      (visit (cdr list)))))

但是，如果您的列表不是循环的但多次包含 相同的元素（如 '(a a b))，您将报告为循环的，因为您检查了数据它仅包含结构而不是结构。不要在此处查看 CAR：

(defun circularp (list)
  (let ((first list))
    (labels ((visit (list)
               (cond
                 ((atom list) nil)
                 ((eq list first) t)
                 (t (visit (cdr list))))))
      (visit (cdr list)))))

此外，内部函数是尾递归，但不能保证 Common Lisp 实现会自动消除尾调用（您应该检查您的实现；大多数可以在要求）。这意味着您可能会分配与列表中的元素一样多的调用堆栈帧，这很糟糕。最好直接使用循环：

(defun circularp (list)
  (loop 
    for cursor on (cdr list)
    while (consp cursor)
    thereis (eq cursor list)))

最后但并非最不重要：您的方法是一种非常常见的方法，但当列表不是一个大的单元格循环链而只是包含某处的循环时失败。考虑例如：

CL-USER> *list*
#1=(A B C . #1#)
CL-USER> (push 10 *list*)
(10 . #1=(A B C . #1#))
CL-USER> (push 20 *list*)
(20 10 . #1=(A B C . #1#))

（请参阅，其中我解释了 #1= 和 #1# 的含义）

前面有数字的列表表现出循环性，但你不能只使用第一个 cons 单元格作为标记，因为你将在循环的子列表中永远循环。这就是龟兔赛跑算法解决的问题（可能还有其他技术，最常见的是将访问过的元素存储在散列中 table）。

在你上次编辑之后，如果我想以递归方式检查循环性，没有 labels:

，我会这样做

(defun circularp (list &optional seen)
  (and (consp list)
       (or (if (member list seen) t nil)
           (circularp (cdr list) (cons list seen)))))

我们在 seen 中跟踪所有访问过的 cons 单元格，这是可选的并初始化为 NIL（您可以传递另一个值，但这可以看作是一个功能）。

然后，如果列表是一个 cons cell，则我们说它是 circular respect to seen：(i) 已经存在于 seen 中，或者 (ii) 是这样它的 CDR 就 (cons list seen).

而言是循环的

这里唯一的额外技巧是确保结果是布尔值，而不是 member 的 return 值（这是要搜索的元素是第一个元素的子列表） : 如果您的环境 *PRINT-CIRCLE* 设置为 NIL 并且列表实际上是循环的，您不希望它尝试打印结果。

代替(if (member list seen) t nil)，您还可以使用：

(when (member list seen))
(position list seen)
当然还有(not (not (member list seen)))

检查 lisp 中的循环性 - 通过递归函数相同的变量

Checking circularity in lisp - same variable through recursive function

lisp

common-lisp

circular-list