檢查列表是否循環的過程（方案）

Question

是否有內置過程來檢查方案（R5RS）中的列表是否循環？何時是循環列表（每個定義）？我試圖找到一些程序來檢查它，以及它是如何實現的，但我一直沒有找到。

Answer 1

如果尾部（最後一個元素）的cdr指向列表的開頭，則列表爲circular per definition。但是，您也可以有一個圓形列表，尾部的cdr指向列表中的任意元素。 A good algorithm檢測循環列表是烏龜和兔子算法。示例實現在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中循環列表的定義是：「循環列表是一個值，使得對於每個n> = 0，cdr^n（x）是一對。這意味着沒有結束的名單。第一對圓形列表不需要是循環的一部分。最終通過跟隨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