时间戳

首页 > 解决方案 > 检查 Common Lisp 中的正确列表

lisp - 检查 Common Lisp 中的正确列表

问题描述

Common Lisp 中是否有一个标准函数可以检查不正确的列表（即循环列表和点列表）而不会发出错误信号？list-length可以检查循环列表（它nil为它们返回），但type-error在给定点列表时发出信号。

Schemelist?遍历整个列表以确保它不是点状的或圆形的；Common Lisplistp只检查它是给定的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))))))

标签： lispcommon-lispcircular-referencecircular-list

解决方案

没有标准的函数可以做到这一点，也许是因为如果要正确的话，这样的函数被认为是相当昂贵的，但实际上，这对我来说似乎是语言的遗漏。

一个最小的（不是非常高效的）实现，它不依赖于处理错误（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。显然，使用哈希表进行发生检查可以做得更好，并且可以使用龟兔算法来避免发生检查（但我不确定它的复杂性是什么）。

我相信图书馆里有比这更好的功能。特别是亚历山大有一个。

在思考这个问题的同时，我也写了这个函数：

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

这可用于获取有关列表的大量信息：它有多长，是否合适，是否不是循环，以及循环在哪里。请注意，在循环列表的情况下，这将返回循环结构作为其第三个值。我相信您需要使用发生检查来执行此操作 - 龟兔赛跑会告诉您列表是否是循环的，但不会告诉您循环的开始位置。

推荐阅读