2

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

我一直在看这里给出的 flatten 函数（它是如此广泛可用）：

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

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

4

3 回答 3

4

在我的日子里，而不是(loop for a in l appending (g a))我们写的(mapcan #'g l)。(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))，即参数列表中只有原子。该列表中的每个原子都包含在一个列表中 - 成为一个单例 列表，(1) (2)等等。然后它们都附加在一起，给我们返回......原始列表：

(  1   2   3   4   5  )

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

(  1   2   3   4   5  )

因此，展平原子列表是一种恒等运算（在 Common LISP 中，即#'identity）。现在想象展平一个包含一些原子的列表以及一个原子列表。同样，列表的每个元素都被转换，然后它们都被附加在一起。正如我们刚刚看到的，原子列表保持原样。每个原子都包含在一个列表中。因此，追加将返回嵌套列表中两个级别上的所有原子，现在已展平：flatten

(  11   12  (1 2 3 4)  13  )

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

(  11   12   1 2 3 4   13  )

依此类推，还有更多级别的嵌套。

NILs 作为列表中的元素会带来问题。NIL是一个空列表，空列表不包含任何内容，因此不应贡献任何内容。但NIL也是一个原子。所以我们为它做了一个特殊的例子，不要把它包含在一个单例列表中——让它保持原样，所以当它被附加时，它就会消失。

于 2012-05-05T20:55:27.950 回答
3 
(defun flatten (l)

上面定义了一个FLATTEN带有一个参数的函数，称为L.

  (cond

如果

    ((null l) nil)

参数的L值为空列表，返回空列表。

    ((atom l) (list l))

或者如果参数L是一个原子（即不是一个列表），则返回一个以原子作为其唯一项的列表。

    (t

否则我们有一个非空列表

       (loop for a in l

然后遍历列表中的所有项目，这是L

        appending (flatten a)

并附加展平每个列表项的结果。

))))
于 2012-05-05T21:24:45.700 回答
2

  1. 如果您正在查看的元素是nil- 它是列表的末尾，则返回 nil。

  2. 如果您正在查看的元素不是列表，则返回包含该元素的列表（我实际上不确定这是正确的做法，因为给定一个不是列表的原子，它将返回一个列表，其中包含原子，而不是原子本身）。

  3. 否则（如果它是一个列表），遍历它的所有元素并附加所有展平的子树（您通过调用展平flatten），然后返回它们。

这很短，但不是最有效的算法，因为 append 需要一直到列表的末尾才能将一个部分放在另一部分的尾部。下面稍微复杂一些，但看起来更高效：

(defun flatten (x &optional y)
  (cond
    ((null x)
     (cond
       ((null y) nil)
       ((listp (car y))
        (flatten (car y) (cdr y)))
       (t (cons (car y) (flatten (cdr y))))))
    ((listp (car x))
     (flatten (car x) (if y (list (cdr x) y) (cdr x))))
    (t (cons (car x) (flatten (cdr x) y)))))

此函数背后的算法执行以下操作：

  1. 如果我们既没有第一个元素，也没有其他元素 - 我们做了所有事情，所以只需返回nil（列表末尾）。

  2. 如果没有第一个元素 - 将第二个元素拆分为第一个元素和其余元素并重复。

  3. 如果有第一个元素，则将其放入列表中，如果有第二个元素 - 保留它，否则，选择下一个元素并重复。

编辑：我改变了#3，因为解释真的很模糊/可能是错误的。

于 2012-05-05T20:35:56.813 回答