检查Common Lisp中的正确列表 [英] Check for proper list in Common Lisp

问题描述

Common Lisp中是否有一个标准功能可以检查不正确的列表(即循环列表和点分列表)而不会发出错误信号? list-length可以检查循环列表(为循环列表返回nil)，但是在给出点列表时发出type-error信号.

Is there a standard function in Common Lisp that can check against improper lists (i.e. circular and dotted lists) without signaling an error? list-length can check against circular lists (it returns nil for them), but signals type-error when given a dotted list.

方案的list?遍历整个列表，以确保它不是点缀或圆形的； Common Lisp的listp仅检查是否已给定nil或cons单元格.

Scheme's list? traverses the whole list to make sure it is not dotted or circular; Common Lisp's listp only checks that it's given nil or a cons cell.

这是我想出的最简单的方法:

Here's the simplest I could come up with:

(defun proper-list-p (x)
  (not (null (handler-case (list-length x) (type-error () nil)))))

由于已经提出了几种实现方式，并且发现了许多意想不到的问题，所以这里是有抱负的proper-list-p作家的测试套件:

Since several implementations have been suggested and many unexpected problems have been found, here's a test suite for aspiring proper-list-p writers:

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

推荐答案

没有标准函数可以执行此操作，可能是因为如果正确的话，该函数被认为是相当昂贵的，但是，实际上，这似乎就像我对语言的遗忘.

There is no standard function to do this, perhaps because such a function was seen as rather expensive if it was to be correct, but, really, this just seems like am omission from the language to me.

一个不依赖处理错误的最小实现(不是很高效)(Python人认为这是一种合理的编程方式，尽管这是一种风格选择，但我不这样做)，是

A minimal (not very performant) implementation, which does not rely on handling errors (Python people think that's a reasonable way to program, I don't, although this is a stylistic choice), is, I think

(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的长度成正比.显然，使用哈希表进行发生检查可以做得更好，并且可以使用乌龟和兔子算法来避免发生检查(但我不确定这样做的复杂性是什么了不起)

This takes time quadratic in the length of l, and conses proportional to the length of l. You can obviously do better using an hashtable for the occurs check, and you can use a tortoise-&-hare algorithm do avoid the occurs check (but I'm not sure what the complexity of that is off the top of my head).

我确信库中有比这更好的功能.特别是亚历山大有一个.

I am sure there are much better functions than this in libraries. In particular Alexandria has one.

在考虑这个问题的同时，我还编写了以下函数:

While thinking about this question, I also wrote this function:

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

这可用于获取有关列表的大量信息:多长时间(如果合适)，是否(如果不是周期性的)以及周期在哪里.注意，在循环列表的情况下，这将返回循环结构作为其第三个值.我认为您需要使用发生检查来执行此操作-乌龟和龟兔子会告诉您列表是否是循环的，但不会告诉您循环的开始位置.

This can be used to get a bunch of information about a list: how long it is, if it is proper, if not if it's cyclic, and where the cycle is. Beware that in the cases of cyclic lists this will return circular structure as its third value. I believe that you need to use an occurs check to do this – tortoise & hare will tell you if a list is cyclic, but not where the cycle starts.

这篇关于检查Common Lisp中的正确列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！