在Common Lisp中找到列表中最嵌套的列表

Question

我是Common Lisp和函数式编程的新手,但我在C,C++,C#,Java等语言方面有很多经验.我在列表中找到最嵌套的列表时遇到了麻烦.我的输入是这样的:

(0 1 (2 3) 4 (5 (6 (7) 8)) 9)

我想获得这个列表中最嵌套的列表,在这种情况下是

(7)

我确实有一个想法,我可以以某种方式压扁列表,直到只剩下一个子列表.为了说明我的意思,这里有几个步骤:

第1步 - 输入:

(0 1 (2 3) 4 (5 (6 (7) 8)) 9)

第2步 - 在"第一级"上展平:

(0 1 2 3 4 5 (6 (7) 8) 9)

第3步 - 在"第二级"上展平:

(0 1 2 3 4 5 6 (7) 8 9)

现在只剩下一个嵌套列表,这意味着这是最嵌套的列表.但是我发现这里有两个或更多这样的列表会出现问题.请分享您对此的看法.

我在Common Lisp中将此过程变为现实时遇到了问题,所以我会感谢一些正确方向的指针,可能是一些示例代码等等.这是一项家庭作业,所以我真的不希望有一个完整的解决方案,但如果有人指出可能是一个更简单,更好的解决方案及其实施,那将会很高兴.

Answer 1

这是我的 CL 解决方案（不是很干净）：

(defun deepest-list (lst)
  (let ((max-depth 0) ret)
    (labels ((inner-deepest-lst (lst depth)
           (cond
         ((null lst) depth)
         ((listp (car lst))
          (let ((local-max (max
                    (inner-deepest-lst (first lst) (1+ depth))
                    (inner-deepest-lst (rest lst)  (1+ depth)))))
            (and (> local-max max-depth) (setf ret (first lst) max-depth local-max))
            local-max))
         (t (inner-deepest-lst (rest lst) depth)))))
      (inner-deepest-lst lst 1))
    ret))

编辑：

经过再三思考，这是一个稍微干净一点的解决方案：

(defun deepest-list (lst)
  (labels ((dl (lst depth)
         (cond
           ((atom lst) (cons 0 lst))
           ((every #'atom lst) (cons depth lst))
           (t (funcall (lambda (x y) (if (> (car x) (car y)) x y))
               (dl (car lst) (1+ depth))
               (dl (cdr lst) depth))))))
    (rest (dl lst 0))))