LISP 确定列表的深度

Question

我正在尝试编写一个函数来确定列表的深度。所以对于

(1 2 3 4) => 1
(1 2 3 (4) ) => 2
(1 2 3 (4 (5))) => 3

等等。

这是我到目前为止所写的内容，它仅适用于线性列表 (depth = 1) 和 depth = 2[= 的列表29=]。

我认为我接近正确的解决方案，但我觉得我遗漏了一些东西..

(defun detlen (lst count) ( cond ((null lst) count) ((LISTP (car lst)) (setq count (+ count 1)) (detlen (cdr lst) count)) (t (detlen (cdr lst) count)) ) )

Answer 1

列表的深度是：

(+ 1 (reduce #'max (mapcar #'depth list) :initial-value 0))

计算所有深度，然后取最大值。加一个。非列表的深度为 0。

CL-USER 195 > (defun depth (list)
                (if (listp list)
                    (+ 1 (reduce #'max (mapcar #'depth list)
                                 :initial-value 0))
                    0))
DEPTH

CL-USER 196 > (depth '(((2)) (1)))
3

Answer 2

我在考虑这个，我意识到你可以很好地概括它。如果你有两个操作，along 沿着某个对象移动光标anddownwhich moves down into elements of it, as well as anapplicable?predicate which tells you ifdowncan be called, then you can write this rather general function to compute thedown`-depth of something (this在 Racket 中，因为 Lisp-1-ness 而更容易）：

(define (dual-depth thing down along applicable?)
  ;; given dual operations down and along, and a test, applicable?,
  ;; return the down depth of thing.
  ;; This is zero if applicable? is false, and can fail to terminate if
  ;; the structure has cycles either in down or along.
  (let dd ([it thing])
    (if (applicable? it)
      (let dd-loop ([tail it] [so-far 0])
        (if (not (applicable? tail))
            so-far
            (dd-loop (along tail) (max so-far (+ 1 (dd (down tail)))))))
      0)))

然后

(define car-depth
  ;; the depth of a cons tree thought of the way it is written
  (λ (l) (dual-depth l car cdr cons?)))

(define cdr-depth
  ;; the depth of a cons tree thought of the other way
  (λ (l) (dual-depth l cdr car cons?)))

甚至：

(define car-depth
  (curryr dual-depth car cdr cons?))

(define cdr-depth
  (curryr dual-depth cdr car cons?))

LISP 确定列表的深度

LISP Determine the depth of a list

lisp

clisp

list

common-lisp

depth