检查列表是否循环的过程（方案）

Question

在 Scheme (R5RS) 中是否有检查列表是否循环的内置程序？什么时候列表是循环的（根据定义）？我试图找到一些程序来检查这个，以及它是如何实现的，但我一直没能找到。

Answer 1

列表是circular per definition if the cdr of the tail (last element) points to the head of the list. However, you can also have a circular list where the cdr of the tail points to an arbitrary element in the list. A good algorithm to detect a circular list is the tortoise and hare algorithm. An example implementation is given at this page。

代码如下（感谢上面链接页面的作者）：

编辑: 我修改了代码，因为它包含 Sylwester 指出的错误。

(define (has-cycle-h slow-ls fast-ls)
  (cond
   ((null? fast-ls) #f)
   ((null? (cdr fast-ls)) #f)
   ((eq? slow-ls fast-ls) #t)
   (else (has-cycle-h (cdr slow-ls) (cddr fast-ls)))))

(define (has-cycle? ls)
  (cond
    ((null? ls) #f)
    (else (has-cycle-h ls (cdr ls)))))


;; Create cyclic list
(define l (cons 1 (cons 2 (cons 3 (cons 4 '())))))
(set-cdr! (cdr (cdr (cdr l))) l)
;; Results in:
;+---+    +---+   +---+    +---+
;| 1 +--->| 2 +-->| 3 +--->| 4 |
;+-+-+    +---+   +---+    +-+-+
;  ^                         |  
;  |                         |  
;  +-------------------------+  

(has-cycle? l) ; Evaluates to #t


;; Create list
(define l (cons 1 (cons 2 (cons 3 (cons 4 '())))))
;; Make it circular by pointing the tail to the second element.
(set-cdr! (cdr (cdr (cdr l))) (cdr l))
;; Results in:
;+---+    +---+   +---+    +---+ 
;| 1 +--->| 2 +-->| 3 +--->| 4 |
;+---+    +-+-+   +---+    +-+-+
;           ^                |  
;           |                |  
;           +----------------+
(has-cycle? l) ; Evaluatores to #t

; Regular list
(has-cycle? '(1 1 1 1 1 1 1)) ; Evaluates to #f

没有用于检测循环列表的 BIF。

Answer 2

SRFI 1中有circular-list?谓词。SRFI 1中循环链表的定义是："A circular list is a value such that for every n>=0, cdr^n(x) is a pair."表示没有链表的结尾。循环列表的第一对不需要是循环的一部分。一个人最终跟着cdrs走到一个循环就够了。

SRFI 1 在非循环列表上有这样的描述：

(not (circular-list? x)) = (or (proper-list? x) (dotted-list? x))

SRFI 1 本身不在 R5RS 中，但我知道的所有实现都包含 srfi 1。请注意，如果 srfi1 在运行时实现，则 srfi 1 的 circular-list? 谓词可能比龟兔算法的 Scheme 实现更快。对您选择的实现进行基准测试，以了解您的实现的行为方式。

http://srfi.schemers.org/srfi-1/srfi-1.html#circular-list-p

检查列表是否循环的过程（方案）

Procedure to check if list is cyclic (Scheme)

scheme

list

cyclic

r5rs