检查 Common Lisp 中的正确列表
Check for proper list in Common Lisp
Common Lisp 中是否有一个标准函数可以检查不正确的列表（即循环列表和虚线列表）而不发出错误信号？ list-length 可以检查循环列表（对它们来说 returns nil），但是当给定点列表时会发出信号 type-error。
方案的list?遍历整个列表以确保它不是点状或圆形的； Common Lisp 的 listp 只检查给定的是 nil 还是 cons 单元格。
这是我能想到的最简单的方法：
(defun proper-list-p (x)
(not (null (handler-case (list-length x) (type-error () nil)))))
由于已经提出了几个实施方案并发现了许多意想不到的问题，这里有一个供有抱负的 proper-list-p 编写者使用的测试套件：
(defun circular (xs)
(let ((xs (copy-list xs)))
(setf (cdr (last xs)) xs)
xs))
(assert (eql t (proper-list-p '())))
(assert (eql t (proper-list-p '(1))))
(assert (eql t (proper-list-p '(1 2))))
(assert (eql t (proper-list-p '(1 2 3))))
(assert (not (proper-list-p 1)))
(assert (not (proper-list-p '(1 . 2))))
(assert (not (proper-list-p '(1 2 . 3))))
(assert (not (proper-list-p '(1 2 3 . 4))))
(assert (not (proper-list-p (circular '(1)))))
(assert (not (proper-list-p (circular '(1 2)))))
(assert (not (proper-list-p (circular '(1 2 3)))))
(assert (not (proper-list-p (list* 1 (circular '(2))))))
(assert (not (proper-list-p (list* 1 2 (circular '(3 4))))))
没有标准的功能可以做到这一点，也许是因为如果它是正确的，这样的功能被认为是相当昂贵的，但实际上，对我来说这似乎是语言的遗漏。
一个最小的（不是非常高效的）实现，它不依赖于处理错误（Python 人们认为这是一种合理的编程方式，我不这么认为，尽管这是一种风格选择），是, 我觉得
(defun proper-list-p (l)
(typecase l
(null t)
(cons
(loop for tail = l then (cdr tail)
for seen = (list tail) then (push tail seen)
do (cond ((null tail)
(return t))
((not (consp tail))
(return nil))
((member tail (rest seen))
(return nil)))))))
这花费的时间是 l 长度的二次方，并且与 l 的长度成正比。显然，使用哈希表进行发生检查可以做得更好，并且可以使用龟兔算法来避免发生检查（但我不确定它的复杂性是什么）。
我相信库中有比这更好的功能。特别是 Alexandria 有一个。
在思考这个问题的同时，我也写了这个函数：
(defun classify-list (l)
"Classify a possible list, returning four values.
The first value is a symbol which is
- NULL if the list is empty;
- LIST if the list is a proper list;
- CYCLIC-LIST if it contains a cycle;
- IMPROPER-LIST if it does not end with nil;
- NIL if it is not a list.
The second value is the total number of conses in the list (following
CDRs only). It will be 0 for an empty list or non-list.
The third value is the cons at which the cycle in the list begins, or
NIL if there is no cycle or the list isn't a list.
The fourth value is the number if conses in the cycle, or 0 if there is no cycle.
Note that you can deduce the length of the leading element of the list
by subtracting the total number of conses from the number of conses in
the cycle: you can then use NTHCDR to pull out the cycle."
;; This is written as a tail recursion, I know people don't like
;; that in CL, but I wrote it for me.
(typecase l
(null (values 'null 0 nil 0 0))
(cons
(let ((table (make-hash-table)))
(labels ((walk (tail previous-tail n)
(typecase tail
(null
(values 'list n nil 0))
(cons
(let ((m (gethash tail table nil)))
(if m
(values 'cyclic-list n tail (- n m))
(progn
(setf (gethash tail table) n)
(walk (cdr tail) tail (1+ n))))))
(t
(values 'improper-list n previous-tail 0)))))
(walk l nil 0))))
(t (values nil 0 nil 0))))
这可以用来获取关于列表的一堆信息：它有多长，是否合适，如果不合适，是否循环，以及循环在哪里。请注意，在循环列表的情况下，这将 return 循环结构作为其第三个值。我相信您需要使用发生检查来执行此操作——乌龟和野兔会告诉您列表是否循环，但不会告诉您循环从哪里开始。
此外，有些内容比公认的答案更简洁：
(defun improper-tail (ls)
(do ((x ls (cdr x))
(visited nil (cons x visited)))
((or (not (consp x)) (member x visited)) x)))
(defun proper-list-p (ls)
(null (improper-tail ls)))
或者像这样：
(defun proper-list-p (ls)
(do ((x ls (cdr x))
(visited nil (cons x visited)))
((or (not (consp x)) (member x visited)) (null x))))
已通过所有操作的测试断言
(tailp l (cdr l)) 对于循环列表是 t 但对于非循环列表是 nil。
感谢@tfp 和@RainerJoswig 教我这个 .
因此，您的函数将是：
(defun proper-listp (lst)
(or (null lst) ; either a `'()` or:
(and (consp lst) ; a cons
(not (tailp lst (cdr lst))) ; not circular
(null (cdr (last lst)))))) ; not a dotted list
顺便说一下，我是故意使用 proper-listp 的。正确的是——按照惯例 proper-list-p。但是，此名称已在 CLISP 实现中被占用，原因是 SYSTEM::%PROPER-LIST-P 为什么函数的定义会引发持续错误。
我们在评论区讨论的结论：
tailp 循环列表的行为未定义。所以这个答案是错误的！感谢@Lassi 解决了这个问题！
在我们对 tailp 进行了无望的尝试之后，在这里，使用了
循环列表的清晰表示 :) .
使用正则表达式（检测循环子列表）
(setf *print-circle* t)
(ql:quickload :cl-ppcre)
(defun proper-listp (lst)
(or (null lst) ; either a `'()` or:
(and (consp lst) ; a cons
(not (cl-ppcre::scan "#\d+=(" (princ-to-string lst)))) ; not circular
(null (cdr (last lst)))))) ; not a dotted list
没有正则表达式（无法检测循环子列表）
(defun proper-listp (lst)
(or (null lst) ; either a `'()` or:
(and (consp lst) ; a cons
(not (string= "#" (subseq (princ-to-string lst) 0 1))) ; not circular
(null (cdr (last lst)))))) ; not a dotted list
Common Lisp 中是否有一个标准函数可以检查不正确的列表（即循环列表和虚线列表）而不发出错误信号？ list-length 可以检查循环列表（对它们来说 returns nil），但是当给定点列表时会发出信号 type-error。
方案的list?遍历整个列表以确保它不是点状或圆形的； Common Lisp 的 listp 只检查给定的是 nil 还是 cons 单元格。
这是我能想到的最简单的方法：
(defun proper-list-p (x)
(not (null (handler-case (list-length x) (type-error () nil)))))
由于已经提出了几个实施方案并发现了许多意想不到的问题，这里有一个供有抱负的 proper-list-p 编写者使用的测试套件：
(defun circular (xs)
(let ((xs (copy-list xs)))
(setf (cdr (last xs)) xs)
xs))
(assert (eql t (proper-list-p '())))
(assert (eql t (proper-list-p '(1))))
(assert (eql t (proper-list-p '(1 2))))
(assert (eql t (proper-list-p '(1 2 3))))
(assert (not (proper-list-p 1)))
(assert (not (proper-list-p '(1 . 2))))
(assert (not (proper-list-p '(1 2 . 3))))
(assert (not (proper-list-p '(1 2 3 . 4))))
(assert (not (proper-list-p (circular '(1)))))
(assert (not (proper-list-p (circular '(1 2)))))
(assert (not (proper-list-p (circular '(1 2 3)))))
(assert (not (proper-list-p (list* 1 (circular '(2))))))
(assert (not (proper-list-p (list* 1 2 (circular '(3 4))))))
没有标准的功能可以做到这一点，也许是因为如果它是正确的，这样的功能被认为是相当昂贵的，但实际上，对我来说这似乎是语言的遗漏。
一个最小的（不是非常高效的）实现，它不依赖于处理错误（Python 人们认为这是一种合理的编程方式，我不这么认为，尽管这是一种风格选择），是, 我觉得
(defun proper-list-p (l)
(typecase l
(null t)
(cons
(loop for tail = l then (cdr tail)
for seen = (list tail) then (push tail seen)
do (cond ((null tail)
(return t))
((not (consp tail))
(return nil))
((member tail (rest seen))
(return nil)))))))
这花费的时间是 l 长度的二次方，并且与 l 的长度成正比。显然，使用哈希表进行发生检查可以做得更好，并且可以使用龟兔算法来避免发生检查（但我不确定它的复杂性是什么）。
我相信库中有比这更好的功能。特别是 Alexandria 有一个。
在思考这个问题的同时，我也写了这个函数：
(defun classify-list (l)
"Classify a possible list, returning four values.
The first value is a symbol which is
- NULL if the list is empty;
- LIST if the list is a proper list;
- CYCLIC-LIST if it contains a cycle;
- IMPROPER-LIST if it does not end with nil;
- NIL if it is not a list.
The second value is the total number of conses in the list (following
CDRs only). It will be 0 for an empty list or non-list.
The third value is the cons at which the cycle in the list begins, or
NIL if there is no cycle or the list isn't a list.
The fourth value is the number if conses in the cycle, or 0 if there is no cycle.
Note that you can deduce the length of the leading element of the list
by subtracting the total number of conses from the number of conses in
the cycle: you can then use NTHCDR to pull out the cycle."
;; This is written as a tail recursion, I know people don't like
;; that in CL, but I wrote it for me.
(typecase l
(null (values 'null 0 nil 0 0))
(cons
(let ((table (make-hash-table)))
(labels ((walk (tail previous-tail n)
(typecase tail
(null
(values 'list n nil 0))
(cons
(let ((m (gethash tail table nil)))
(if m
(values 'cyclic-list n tail (- n m))
(progn
(setf (gethash tail table) n)
(walk (cdr tail) tail (1+ n))))))
(t
(values 'improper-list n previous-tail 0)))))
(walk l nil 0))))
(t (values nil 0 nil 0))))
这可以用来获取关于列表的一堆信息：它有多长，是否合适，如果不合适，是否循环，以及循环在哪里。请注意，在循环列表的情况下，这将 return 循环结构作为其第三个值。我相信您需要使用发生检查来执行此操作——乌龟和野兔会告诉您列表是否循环，但不会告诉您循环从哪里开始。
此外，有些内容比公认的答案更简洁：
(defun improper-tail (ls)
(do ((x ls (cdr x))
(visited nil (cons x visited)))
((or (not (consp x)) (member x visited)) x)))
(defun proper-list-p (ls)
(null (improper-tail ls)))
或者像这样：
(defun proper-list-p (ls)
(do ((x ls (cdr x))
(visited nil (cons x visited)))
((or (not (consp x)) (member x visited)) (null x))))
已通过所有操作的测试断言
(tailp l (cdr l)) 对于循环列表是 t 但对于非循环列表是 nil。
感谢@tfp 和@RainerJoswig 教我这个
因此，您的函数将是：
(defun proper-listp (lst)
(or (null lst) ; either a `'()` or:
(and (consp lst) ; a cons
(not (tailp lst (cdr lst))) ; not circular
(null (cdr (last lst)))))) ; not a dotted list
顺便说一下，我是故意使用 proper-listp 的。正确的是——按照惯例 proper-list-p。但是，此名称已在 CLISP 实现中被占用，原因是 SYSTEM::%PROPER-LIST-P 为什么函数的定义会引发持续错误。
我们在评论区讨论的结论：
tailp 循环列表的行为未定义。所以这个答案是错误的！感谢@Lassi 解决了这个问题！
在我们对 tailp 进行了无望的尝试之后，在这里，使用了
循环列表的清晰表示 :) .
使用正则表达式（检测循环子列表）
(setf *print-circle* t)
(ql:quickload :cl-ppcre)
(defun proper-listp (lst)
(or (null lst) ; either a `'()` or:
(and (consp lst) ; a cons
(not (cl-ppcre::scan "#\d+=(" (princ-to-string lst)))) ; not circular
(null (cdr (last lst)))))) ; not a dotted list
没有正则表达式（无法检测循环子列表）
(defun proper-listp (lst)
(or (null lst) ; either a `'()` or:
(and (consp lst) ; a cons
(not (string= "#" (subseq (princ-to-string lst) 0 1))) ; not circular
(null (cdr (last lst)))))) ; not a dotted list