如何在LISP中删除嵌套括号

Question

如何在LISP中删除嵌套括号

19

如何在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

18

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

13个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- coredump · Answer 1

这个常见问题只有递归解法（不包括Rainer的答案）。

让我们来看一个循环版本：

(defun flatten (tree &aux todo flat)
  (check-type tree list)
  (loop
     (shiftf todo tree nil)
     (unless todo (return flat))
     (dolist (elt todo)
       (if (listp elt)
           (dolist (e elt)
             (push e tree))
           (push elt flat))))))

- Bernard Adrian · Answer 2

(defun unnest (somewhat)
  (cond
   ((null somewhat) nil)
   ((atom somewhat) (list somewhat))
   (t
    (append (unnest (car somewhat)) (unnest (cdr somewhat))))))

- mijo888 · Answer 3

我忍不住要加上我的两分钱。虽然CL规范不要求尾调用优化（TCO），但许多（大部分？）实现都具备这个功能。

因此，这里提供一种尾递归版本，将树的叶节点收集到一个扁平列表中（这是“移除括号”的一种版本）：

(defun flatten (tree &key (include-nil t))
  (check-type tree list)
  (labels ((%flatten (lst accum)
             (if (null lst)
                 (nreverse accum)
                 (let ((elem (first lst)))
                   (if (atom elem)
                       (%flatten (cdr lst) (if (or elem include-nil)
                                               (cons elem accum)
                                               accum))
                       (%flatten (append elem (cdr lst)) accum))))))
    (%flatten tree nil)))

默认情况下，它保留空叶节点，并提供删除选项。它还保留树的叶节点从左到右的顺序。

来自Google LISP风格指南的注意事项：应优先选择迭代而不是递归。

...大多数严肃的实现（包括SBCL和CCL）确实实现了正确的尾调用，但有一些限制：

(DECLARE (OPTIMIZE ...))设置必须足够快速并且不过于注重DEBUG，对于某些依赖于编译器的“足够”和“过多”的含义。

来自SBCL文档的内容： ...当调试优化质量大于2时，将禁用尾递归优化。