list - Common Lisp - 编写检测循环列表的函数

Question

我的 CS 函数式语言类(class)有一个作业，我们必须编写一个函数来检测给定列表的开头是否为循环。该函数必须是递归的。我们将其命名为 circular :

* (setf list1 '(a b c d))
* (rplacd (cddr list1) list1)
* list1
#1=(A B C . #1#)
* (circular list1)
t
* (circular '(a b c a b c))
nil

现在，我知道在这种情况下如何检查循环性:在递归的某个时刻，列表中的一个原子和一个cons将共享相同的地址作为列表本身，因此循环。到目前为止，这是我的功能:

(defun circular (list &aux list2)
  (setf list2 list)
  (cond
    ((null list) nil)
    ((eq (car list) list2) t)
    (t (circular (cdr list))) ) )

我认为通过在递归的每个点比较 list 的 car 和 list2 函数最终会返回一个结果，但是虽然该函数确实适用于非循环列表，但当我尝试在循环列表上使用它时，它会变得无限递归。我确信我在这里遗漏了一些非常明显的东西，但仍然非常感谢任何帮助!

Answer 1

可以使用 tortoise and hare algorithm 解决这个问题你有两个光标扫描 tortoise，一次扫描一个缺点，hare 从第二个元素开始以双倍速度扫描。如果乌龟和兔子是同一个元素，那么你就有了一个循环。

(defun cyclicp (list)
  "check if a list is cyclic using tortoise and hare algorithm"
  (loop :for tortoise on list
        :for hare on (cdr list) :by #'cddr
        :thereis (eq tortoise hare)))

假设您有列表，#1=(a b c . #1#) 或更准确地说是 '#1=(a . #2=(b . #3=( c.#1#)))。它包含 3 个地址为 1,2,3 的 cons，每个 cons 都有一个符号值 a, b, c。

如果我写了乌龟和兔子的 car，你会看到兔子绕了一圈，最终以与乌龟相同的 cons 结束

Iteration 1 2 3
Tortoise  a b c
Hare      b a c
              ^ match

您唯一需要做的就是使用递归重新实现它。它看起来像这样:

(defun cyclicp (list)
  "check if a list is cyclic using tortoise and hare algorithm"
  (labels ((aux (tortoise hare)
        (cond ((null hare) <??>)
              ((eq tortoise hare) <??>)
              (t (aux <??> <??>)))))
    (aux list (cdr list))))

编辑

一个简单且简单的版本只检查返回到第一个 cons 的引用可以像这样完成:

(defun cyclic-1-p (list)
  "check if a list is cycles back to the first cons"
  (loop :for cursor on (cdr list)
        :thereis (eq cursor list)))

您唯一需要做的就是使用递归重新实现它。它看起来像这样:

(defun cyclic-1-p (list)
  "check if a list is cycles back to the first cons"
  (labels ((aux (cursor)
        (cond ((null cursor) <??>)
              ((eq cursor list) <??>)
              (t (aux <??>)))))
    (aux (cdr list))))

如果循环发生但不是在第一个 cons 中，这将不会终止。

(cyclic-1-p '(1 . #1=(2 3 . #1#))) ; never halts