时间戳

首页 > 解决方案 > 为什么循环列表在 Scheme 中不被视为列表？

list - 为什么循环列表在 Scheme 中不被视为列表？

问题描述

对于 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?将返回#f.

为什么 Scheme 不将循环列表视为列表？我想这与 list 的正式定义有关，但是 Scheme 是如何制定这样的定义的呢？另外，list?就拥有检测循环列表的属性而言，它是如何实现的？

标签： listschemecircular-listcycle-detection

解决方案

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

  • 空列表，();
  • 或者一对，其 car 是任何对象，其 cdr 是一个列表。

请注意，循环列表不符合此标准，类似(x . y)or之类的也不符合(x y . z)。

我相信这是 R n RS 对至少某些 n 值使用的“列表”的定义（特别是R5RS使用的定义）。同样，R5RS 很清楚，它list?必须为循环列表返回 false（因此特别是它必须具有发生检查或类似的东西）。

历史上其他 Lisp 对此要宽松得多：例如 Common Lisp 定义它listp只是检查一个对象是不是()或者是一个缺点，并将列表定义为该类型的元素。什么 Scheme 称之为“列表” Common Lisp 称之为“正确的列表”。

这是一个list?使用龟兔赛跑算法来检查循环性的版本（这可能不正确，我认为即使是这样也过于复杂，但为时已晚）：

(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]))]))

推荐阅读