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

Question

我有一个CS功能语言类的作业,我们必须编写一个能够检测给定列表在其开头是否为循环的函数.该函数必须是递归的.我们来命名它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

现在,我知道在这种情况下如何检查圆度:在递归的某个点上,列表中的原子 a cons将与列表本身共享相同的地址,因此是圆形度.到目前为止,这是我的功能:

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

我认为通过比较递归的每个点car的list反对list2,函数最终会返回一个结果,但是当函数对非循环列表起作用时,当我尝试在循环列表中使用它时,它会变得无限递归.我确信我错过了一些非常明显的东西,但是,任何帮助都会非常感激!

Answer 1

这个问题可以通过乌龟和野兔算法来解决,在这种算法中你有两个游标一次扫描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 cons与地址1,2,3和每个利弊具有符号值中的一个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