如何在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)
感谢
如何在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)
感谢
(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))))))
(defun unnest (somewhat)
(cond
((null somewhat) nil)
((atom somewhat) (list somewhat))
(t
(append (unnest (car somewhat)) (unnest (cdr somewhat))))))
我忍不住要加上我的两分钱。虽然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时,将禁用尾递归优化。