list - 计算 LISP 中每个级别的子列表

Question

我需要编写一个程序来计算每个级别的子列表并像这样打印

((1 2) (2 1) (3 1))

( (<level> <count>) (<level> <count> ... )

因此，对于 (A (B (C)) D)它将是( (1 1) (2 1) (3 1) )

我写了这个程序。逻辑是我每次切头，检查，如果它是一个列表，我增加计数器，然后将列表的其余部分附加到我的 other部分。否则，只需剪切并继续尾部。

我正在使用 SBCL 并收到此错误:

 debugger invoked on a TYPE-ERROR in thread
 #<THREAD "main thread" RUNNING {1002C0EB73}>:
 The value A is not of type LIST.

这是我的代码:

(defun count-sublists (list)
  (labels
    ((iter (current other count level res)
      (if (null current)
        (if (null other)
          (cons (list level count) res)
          (iter other () 0 (1+ level) (cons (list level count) res)))
      (let ((myhead (car current)) (mytail (cdr current)))
         (if (listp myhead)
           (iter mytail other (1+ count) level res)
           (iter mytail (append myhead other) count level res))))))
      (iter list () 0 1 ())))

 (print (count-sublists '(A (B) C)))

Answer 1

调试你得到的东西

这是您的代码，具有更惯用的格式:

(defun count-sublists (list)
  (labels ((iter (current other count level res)
             (if (null current)
                 (if (null other)
                     (cons (list level count) res)
                     (iter other () 0 (1+ level) (cons (list level count) res)))
                 (let ((myhead (car current))
                       (mytail (cdr current)))
                   (if (listp myhead)
                       (iter mytail other (1+ count) level res)
                       (iter mytail (append myhead other) count level res))))))
    (iter list () 0 1 ())))

您可以通过更简单的测试得到相同的错误消息:

(count-sublists '(a))

更简单的测试可以更容易地推断会发生什么。

1. 检查是否'(a)一片空白。不是，所以
2. 你得到 myhead = a , 和 mytail = '() .
3. 检查是否a是一个列表。不是这样的
4. 做 (iter mytail (append myhead other) ...) , 但是
5. append将列表作为参数，你已经知道 myhead不是列表。

使用 (list* myhead other)或 (cons myhead other)或 (append (list myhead) other)相反。

使用系统调试器

错误消息使您看起来像是在使用 SBCL，在这种情况下，您可以编写代码进行调试优化，然后回溯会更有帮助。首先，将您的代码更改为

(defun count-sublists (list)
  (declare (optimize debug))
  ; ...

然后，当您运行测试并收到错误时，您可以键入 BACKTRACE 并获取指向您的信息 append :

debugger invoked on a TYPE-ERROR in thread
#<THREAD "main thread" RUNNING {1002FDE853}>:
  The value A is not of type LIST.

Type HELP for debugger help, or (SB-EXT:EXIT) to exit from SBCL.

restarts (invokable by number or by possibly-abbreviated name):
  0: [RETRY   ] Retry EVAL of current toplevel form.
  1: [CONTINUE] Ignore error and continue loading file "/home/taylorj/tmp/count-levels.lisp".
  2: [ABORT   ] Abort loading file "/home/taylorj/tmp/count-levels.lisp".
  3:            Exit debugger, returning to top level.

(SB-IMPL::APPEND2 #<unavailable argument> #<unavailable argument>) [tl,external]
0] BACKTRACE

Backtrace for: #<SB-THREAD:THREAD "main thread" RUNNING {1002FDE853}>
0: (SB-IMPL::APPEND2 #<unavailable argument> #<unavailable argument>) [tl,external]
1: ((LABELS ITER :IN COUNT-SUBLISTS) (A) NIL 0 1 NIL)
2: (COUNT-SUBLISTS (A))
; ...

更地道的解决方案

要提出一个特别优雅的解决方案，这不是一个容易的问题，但这里有一种相当有效的方法。它创建了一个将深度映射到出现次数的哈希表(即，它本质上是一个直方图)。

(defun count-sublists (object &aux (table (make-hash-table)) (max 0))
  (labels ((incf-depth (depth)
             (setf max (max max depth))
             (incf (gethash depth table 0)))
           (map-depth (object depth)
             (when (listp object)
               (incf-depth depth)
               (dolist (x object)
                 (map-depth x (1+ depth))))))
    (map-depth object 1)
    (loop for depth from 1 to max
       collecting (list depth (gethash depth table 0)))))

(count-sublists '(A (B) C))
;=> ((1 2) (2 1))

(count-sublists '(A (B (C)) D))
;=> ((1 2) (2 1) (3 1))

(count-sublists '(a (((b c))) d))
;=> ((1 1) (2 1) (3 1) (4 1))