lisp - 检查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)))
        ) ) ) ) )

它没有给出预期的结果，但我不明白我的错误在哪里

我不确定我是否正确使用了“标签”

有没有办法在不使用“标签”的情况下做到这一点？

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

(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 , 绑定(bind)到 list .我想你想定义 first如(car list) .

您定义一个本地 circ2功能，但从不使用它。我希望 circularp函数(-p 用于“谓词”，如 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#))

(见 that answer 我解释了 #1= 和 #1# 的含义)

前面带有数字的列表表现出循环性，但您不能只使用第一个 cons 单元格作为标记，因为您将在循环的子列表中永远循环。这就是 Tortoise and Hare 算法解决的问题(可能还有其他技术，最常见的是将访问过的元素存储在哈希表中)。

在您最后一次编辑之后，如果我想以递归方式检查循环性，而不需要 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 单元格，我们就说它是循环的，如果它是:(i)已经存在于 seen 中，或者(ii)它的 CDR 相对于 (cons list seen) 是循环的。 .

这里唯一的附加技巧是确保结果是 bool 值，而不是 member 的返回值。 (这是要搜索的元素是第一个元素的子列表):如果您的环境有 *PRINT-CIRCLE*设置为 NIL 并且列表实际上是循环的，您不希望它尝试打印结果。

而不是 (if (member list seen) t nil) ，你也可以使用:

(when (member list seen))

(position list seen)

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