lisp - Lisp 中的 Flatten Nests 函数 - 需要帮助理解

Question

我一直在尝试寻找一种方法将嵌套列表压缩为返回原始列表中的数字，但我遇到了一些麻烦。

我一直在研究这里给出的 flatten 函数(它被广泛使用):

(defun flatten (l)
  (cond
    ((null l) nil)
    ((atom l) (list l))
    (t (loop for a in l appending (flatten a)))))

我知道这个例子是递归的，但它是如何工作的？它检查元素是否为 null 或原子，但如果元素符合这些条件，它会做什么？

Answer 1

在我的时代，我们编写了 (mapcan #'g l) 而不是 (loop for a in l appending (g a))。这相当于 (apply #'append (mapcar #'g l))，或多或少:

(defun flatten (l) 
    (if l 
        (if (atom l) 
            (list l) 
            (mapcan #'flatten l))))

那么在这种情况下这意味着什么？假设您调用 (flatten (list 1 2 3 4 5))，即参数列表中只有 atoms。 每个 列表中的原子都包含在一个列表中——成为一个单例 列表，如(1) (2) 等。然后将它们全部附加在一起，返回给我们……原始列表:

(  1   2   3   4   5  )

( (1) (2) (3) (4) (5) )

(  1   2   3   4   5  )

因此，将原子列表展平是一种恒等操作(在 Common LISP 中，即 #'identity)。现在想象一下将一个包含一些 atoms 的列表以及 atoms 的 list 展平。同样，列表中的每个元素都通过 flatten 进行转换，然后将它们全部附加在一起。正如我们刚刚看到的，原子列表保持不变。 原子 分别包含在一个列表中。所以追加将返回嵌套列表中两个层上的所有原子，现在已展平:

(  11   12  (1 2 3 4)  13  )

( (11) (12) (1 2 3 4) (13) )

(  11   12   1 2 3 4   13  )

以此类推，还有更多层次的嵌套。

NIL 作为列表中的元素会带来问题。 NIL 是一个空列表，空列表不包含任何内容，因此不应提供任何内容。但是 NIL 也是一个原子。所以我们为它做了一个特例，不将它包含在一个单例列表中 - 保持原样，这样当附加时，它就会消失。