如何在LISP中删除嵌套括号

Question

如何在Common LISP中递归地移除嵌套的括号，例如：

  (unnest '(a b c (d e) ((f) g))) => (a b c d e f g)
  (unnest '(a b))                 => (a b)
  (unnest '(() ((((a)))) ()))     => (a)

感谢

- bubdada

---

不要去掉括号。 括号只是列表的打印表示中的一部分。您现在正在对列表进行扁平化处理。 - Svante

Answer 1

我会这样做：

(ql:quickload "alexandria")
(alexandria:flatten list)

这主要有效是因为我已经安装了Quicklisp。

- Xach

---

太谦虚了！这主要是因为您已经创建了Quicklisp。 - Joe Taylor

Answer 2

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

- Donnie Cameron

---

因为你附加的所有列表都来自第3行中的list调用，所以你可以使用nconcing而不是appending。 - Dan Robertson

Answer 3

我知道这是一个旧的帖子，但当我谷歌搜索Lisp flatten时，它是首先出现的。我发现的解决方案与上面讨论的类似，但格式略有不同。我将把它解释为如果你是新手，就像我第一次谷歌这个问题时一样，所以其他人也可能是。

(defun flatten (L)
"Converts a list to single level."
    (if (null L)
        nil
        (if (atom (first L))
            (cons (first L) (flatten (rest L)))
            (append (flatten (first L)) (flatten (rest L))))))

对于那些不熟悉Lisp的人，这里是简要说明。

下面这行声明一个名为flatten的函数，其参数为L。

(defun flatten (L)

下面的代码用于检查空列表。

    (if (null L)

下一行返回nil，因为cons ATOM nil声明了一个只有一个条目（ATOM）的列表。这是递归的基本情况，并让函数知道何时停止。此后的行检查列表中的第一个项目是否为原子而不是另一个列表。

        (if (atom (first L))

然后，如果是原子，它使用递归来创建与函数将生成的其余扁平化列表相结合的此原子的扁平化列表。cons将一个原子与另一个列表组合在一起。

            (cons (first L) (flatten (rest L)))

如果不是原子，则需要对其进行展平，因为它是另一个可能包含进一步列表的列表。

            (append (flatten (first L)) (flatten (rest L))))))

append函数会将第一个列表追加到第二个列表的开头。还要注意，在Lisp中每次使用函数都必须用括号括起来。这一点一开始让我很困惑。

- user977221

---

它是尾递归吗？ - user4813927

它不是尾递归，而且问题也不重要：CL规范对尾调用消除没有任何要求，因此不能依赖它。这将在长列表和深列表中都会出现问题。另一个答案中使用循环的解决方案只会在深列表中出现问题。 - Dan Robertson

Answer 4

例如，您可以这样定义它：

(defun unnest (x)
  (labels ((rec (x acc)
    (cond ((null x) acc)
      ((atom x) (cons x acc))
      (t (rec (car x) (rec (cdr x) acc))))))
    (rec x nil)))

- Jakob

Answer 5

(defun flatten (l)
  (cond ((null l) nil)
        ((atom (car l)) (cons (car l) (flatten (cdr l))))
        (t (append (flatten (car l)) (flatten (cdr l))))))

- Bill

Answer 6

Lisp有一个函数remove用于移除元素。这里我使用了一个版本的REMOVE-IF，它可以移除每个满足谓词条件的项。我测试如果该元素是括号，则将其移除。

如果你想要移除括号，请看这个函数：

(defun unnest (thing)
  (read-from-string
   (concatenate
    'string
    "("
    (remove-if (lambda (c)
                 (member c '(#\( #\))))
               (princ-to-string thing))
    ")")))

请注意，正如Svante所提到的那样，通常不会“删除”括号。

- Rainer Joswig

Answer 7

大多数答案已经提到了一个递归解决Flatten问题的方法。使用通用Lisp对象系统的多重分派，你可以通过为三种可能情况定义3种方法来递归解决该问题：

(defmethod flatten ((tree null))
  "Tree is empty list."
  ())
(defmethod flatten ((tree list))
  "Tree is a list."
  (append (flatten (car tree))
          (flatten (cdr tree))))
(defmethod flatten (tree)
  "Tree is something else (atom?)."
  (list tree))

(flatten '(2 ((8) 2 (9 (d (s (((((a))))))))))) ; => (2 8 2 9 D S A)

- Student

Answer 8

我留在这里的原因是我阅读这个问题时只需要将一级展平，后来自己发现在这种情况下 (apply 'concatenate 'list ((1 2) (3 4) (5 6 7)))是一个更干净的解决方案。

- Isti115

Answer 9

这是一种基于累加器的方法。本地函数%flatten保留了一个尾部的累加器（已经被展平的列表的右侧部分）。当要展平的部分（列表的左侧部分）为空时，它返回尾部。当要展平的部分是非列表时，它返回该部分前缀加到尾部上。当要展平的部分是一个列表时，它会将列表的其余部分（带有当前尾部）展平，然后使用该结果作为尾部来展平列表的第一部分。

(defun flatten (list)
  (labels ((%flatten (list tail)
             (cond
               ((null list) tail)
               ((atom list) (list* list tail))
               (t (%flatten (first list)
                            (%flatten (rest list)
                                      tail))))))
    (%flatten list '())))

CL-USER> (flatten '((1 2) (3 4) ((5) 6) 7))
(1 2 3 4 5 6 7)

- Joshua Taylor

Answer 10

我知道这个问题实际上很古老，但我注意到没有人使用推送/反转惯用语，所以我在这里上传了它。

函数reverse-atomize会将每个"原子"取出并放入下一个调用的output中。最后，它会产生一个倒序的扁平化列表，这可通过atomize函数中的nreverse函数解决。

(defun reverse-atomize (tree output)
    "Auxillary function for atomize"
    (if (null tree)
      output
      (if (atom (car tree))
          (reverse-atomize (cdr tree) (push (car tree) output))
          (reverse-atomize (cdr tree) (nconc (reverse-atomize (car tree)
                                                               nil)
                                              output)))))

(defun atomize (tree)
    "Flattens a list into only the atoms in it"
     (nreverse (reverse-atomize tree nil)))

因此，调用atomize '((a b) (c) d)的样子是这样的：

(A B C D)

如果您使用 reverse-atomize '((a b) (c) d) 调用 reverse-atomize，将会发生以下情况：

(D C B A)

人们喜欢使用push、nreverse和nconc等函数，因为它们使用的RAM比它们各自对应的cons、reverse和append函数少。话虽如此，reverse-atomize具有双重递归性质，会带来其自身的RAM问题。

- Spenser Truex