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

Answer 2

您迭代地展平列表的方法可能应该可以正常工作，尽管这不是最有效或（主观上）优雅的方法。

如果有多个这样的列表，正确的输出将取决于规范——您应该返回所有列表，还是只返回第一个列表，或者抛出错误？

如果我是你，我会考虑提出一个递归函数来解决这个问题。每个级别的递归基本上都会处理嵌套列表的给定级别的元素。想想每个递归调用应该做什么——如果一旦点击，那就非常简单了！

Answer 3

这是我的解决方案，使用与OP类似的方法。 （对于多个最深的项目，它们都会被返回。）

我用Scheme编写它，它可能不会立即翻译成Common Lisp，所以我不认为它是一个完整的赠品。不过，它有可能会剧透，所以请谨慎行事。

(define (deepest lst)
  (let ((filtered (filter pair? lst)))
    (cond ((null? filtered) lst)
          (else (deepest (concatenate filtered))))))