为什么循环列表不被视为 Scheme 中的列表？

Question

我还没有发现关于 Scheme 编程语言的任何问题，所以我希望这不是重复的。

在尝试使用解释器时，我遇到了一个奇怪的事件：

(define li (list 'a 'b 'c 'd 'e))

(list? li)
;; -> #t

(set-cdr! (cddddr li) li) ;; list is now circular

(list? li)
;; -> #f

显然，在将列表对象更改为循环后，list? 将 return #f.

为什么 Scheme 不把循环列表当作列表？我猜这与列表的正式定义有关，但是Scheme是如何制定这样的定义的呢？另外，list? 是如何实现的属性检测循环列表？

Answer 1

我认为列表的自然定义是列表是：

空列表，()；
或者一对car是任意对象，cdr是列表的一对。

请注意，循环列表不符合此条件，(x . y) 或 (x y . z).

等内容也不符合此条件

我相信这是 RⁿRS 对至少某些 n 值使用的 'list' 的定义（特别是 R5RS). R5RS 再次明确，对于循环列表，list? 必须 return false（因此特别是它必须具有发生检查或类似的东西）。

其他 Lisp 在历史上对此更为宽松：例如 Common Lisp 定义它是 listp 只是检查一个对象是 () 还是一个 cons，并将列表定义为元素那种。 Scheme 调用的内容 'lists' Common Lisp 调用的内容 'proper lists'.

这里是 list? 的一个版本，它使用 tortoise-and-hare 算法来检查循环性（这可能不正确，我认为即使是这样也过于复杂，但已经晚了）：

(define (lyst? l)
  (cond
    [(null? l)
     #t]
    [(not (cons? l))
     #f]
    [else
     (let lyst-loop? ([tortoise l]
                      [hare (cdr l)])
       (cond [(eq? hare tortoise)
              #f]
             [(null? hare)
              #t]
             [(cons? hare)
              (cond [(null? (cdr hare))
                     #t]
                    [(not (cons? (cdr hare)))
                     #f]
                    [else
                     (lyst-loop? (cdr tortoise)
                                 (cdr (cdr hare)))])]
             [else
              #f]))]))

为什么循环列表不被视为 Scheme 中的列表？

Why aren't cyclic lists considered lists in Scheme?

scheme

list

circular-list

cycle-detection