list - Common lisp 树中的最低级别

Question

我正在尝试编写代码来查找树中的最小级别(嵌套子列表的最小数量) 树是这样给出的:

(A (B (E (I))(F))(C (G))(D)) 

看起来像:

      A
   /  |  \
  B   C   D
 /\   |   
E  F  G   
|
I

这会导致...级别 1。最高级别是级别 3，但我只需要最低级别。

我尝试使用 min 函数，但无论我做什么，它都会返回 1 或 0，因为如果列表为空，我返回 0 并且 min(0 或任何东西)始终为 0。关于如何在不映射的情况下解决此问题的任何想法/lambda 函数？

我试过这样做:

(defun nrlevels (tail)
  (cond
    ((null tail) 0)
    ((listp (car tail))
     (min (+ 1 (nrlevels (car tail)))
          (nrlevels (cdr tail)))) 
    (t (nrlevels (cdr tail)))))

但正如我所说，min 将(最终)比较 0 和 0 是最小值，最终结果将是 0。我不知道如何跳出这个循环。

Answer 1

您将级别递归和表示对节点子节点的迭代的递归都放入单个递归中。问题是区分没有 child 的访问节点和已经到达 child 列表末尾的访问节点。

你需要把这些东西分开。我发现将对子列表的迭代放入一个循环中是最简单的:

(defun minimum-child-level (tree)
  (if (atom tree)
      0
      (1+ (loop :for child :in tree
                :when (listp child)
                :minimize (minimum-child-level child)))))

或减少:

(defun minimum-child-level (tree)
  (if (atom tree)
      0
      (1+ (reduce #'min
                  (mapcar #'minimum-child-level
                          (remove-if-not #'listp tree))))))

编辑:您可以通过解释 min 累加器并以一种或另一种方式递归来完成此操作，但我不建议将此用于生产代码:

(defun minimum-child-level (tree &optional min-so-far)
  (cond ((endp tree)         ; end of child list
         (if min-so-far
             (1+ min-so-far) ; there were children
             0))             ; no children
        ((atom (first tree)) ; ignore symbols, go to next child
         (minimum-child-level (rest tree) min-so-far))
        (t                   ; sublist
         ;; recurse into child
         (let ((child-minlevel (minimum-child-level (first tree))))
           ;; go to next child
           (minimum-child-level (rest tree)
                                (if min-so-far
                                    (min min-so-far child-minlevel)
                                    child-minlevel))))))