使用普通的口齿不清来压平列表

Question

我正在读Paul Graham的《Lisp论》一书。在第4章"实用函数"中，他给出了在列表上操作的小函数的例子，这对编写更大的程序很有帮助。

其中之一是CCD_ 1。给定任意级别的嵌套列表作为参数，flatten将删除所有嵌套元素，并将它们放在顶层。

以下是我尝试实现扁平化：

(defun flatten (lst)
  (labels ((rflatten (lst1 acc)
                     (dolist (el lst1)
                       (if (listp el)
                         (rflatten el acc)
                         (push el acc)))
                     acc))
    (reverse (rflatten lst nil))))

但是上面的函数不能正确地压平列表。

; returns (1) instead of (1 2)
(print (flatten '(1 (2))))
(1)

用(1 (2))调用函数会返回(1)而不是(1 2)。

我找不到我的flatten实现有什么问题。这是我使用的方式吗labels？还是我使用dolist宏的方式？dolist宏始终返回nil。但这并不重要，因为我正在使用累加器acc来存储扁平列表。

Answer 1

flatten0更改范围中的符号绑定。因此，递归(rflatten el acc)有它自己的acc，这是那里的结果，但你不会对返回的结果做任何事情，它也不会改变被调用方acc。

也许(setf acc (rflatten el acc))可以解决这个问题：

(defun flatten (lst)
  (labels ((rflatten (lst1 acc)
             (dolist (el lst1)
               (if (listp el)
                   (setf acc (rflatten el acc))
                   (push el acc)))
             acc))
    (reverse (rflatten lst nil))))

Answer 2

您实际上非常接近。正如Sylwester提到的，问题是（push-el-acc）仅修改el的本地绑定（其中，对rflatten的每次调用都有一个新函数。正如Rainer所提到的，它并不是传统意义上的累加器，所以我不会称它为acc，而是result。由于您已经在定义本地函数，因此没有理由不在更大的范围内定义result：

(defun flatten (lst)
  (let ((result '()))
    (labels ((rflatten (lst1)
               (dolist (el lst1)
                 (if (listp el)
                   (rflatten el)
                   (push el result)))))
      (rflatten lst)
      (nreverse result))))

实际上也有几种方法可以解决这个问题。第一个是风格和品味的问题，但我会使用&aux变量绑定结果，因此

(defun flatten (lst &aux (result '()))
  ...)

下一个是dolist可以采用第三个参数，一种用于计算返回值的形式。这通常用于"推送创建列表，然后反转返回值"的习惯用法，例如

(let ((result '()))
  (dolist (x list (nreverse result))
    ...
    (push ... result)))

您不想在每个dolist之后反转，但您仍然可以从doliststrong>结果，从而从rflatten返回。然后，您可以简单地调用nrives，得到rflatten的结果：

(defun flatten (lst &aux (result '()))
  (labels ((rflatten (lst1)
             (dolist (el lst1 result)
               (if (listp el)
                 (rflatten el)
                 (push el result)))))
      (nreverse (rflatten lst))))

Answer 3

一个非递归代码，它通过conses、遵循注释并从用户的代码开始构建结果：Sylwester:

(defun flatten (lst &optional back acc)
  (loop
     (cond 
        ((consp lst) (psetq lst (cdr lst)              ; parallel assignment
                           back (cons (car lst) back)))
        (back
                  (if (consp (car back))  
                    (psetq lst (cdar back)
                          back (cons (caar back) (cdr back)))
                    (psetq acc (if (car back) (cons (car back) acc) acc)
                          back (cdr back))))
        (t     
               (return acc)))))                        ; the result

它不漂亮，但似乎很管用。并行分配PSETQ用于模拟尾部递归调用帧更新，而不必担心精确的排序。

实现与良好编码的过程相同的过程

(defun flatten2 (l z)
    (cond
        ((endp l) z)
        ((listp (car l)) (flatten2 (car l) (flatten2 (cdr l) z)))
        ((atom (car l)) (cons (car l) (flatten2 (cdr l) z)))))
(defun flatten (l)
   (flatten2 l nil))

隐式堆栈操作被解释为变量之间的列表结构操作。

Answer 4

我发现了一个不使用辅助函数或变量赋值的解决方案，并以向前的方式构建列表，我认为这更容易理解。

(defun flatten (lst &aux (re '()))
  (cond
    ((null lst) '())
    ((listp (car lst))
     (append (flatten (car lst))
             (append (flatten (cdr lst))
                     re)))
    (t (cons (car lst)
             (append (flatten (cdr lst)) re)))))

我们可以很容易地调整它来控制压扁的深度！

(defun flatten* (lst depth &aux (re '()))
  (cond
    ((null lst) '())
    ((listp (car lst))
     (append (cond
               ((= 0 depth)             ; flatten none
                (list (car lst)))
               ((< 0 depth)             ; flatten down
                (flatten* (car lst) (- depth 1)))
               ((= -1 depth)            ; flatten all
                (flatten* (car lst) depth))
               ((< depth -1)            ; flatten up
                (list (flatten* (car lst) (+ depth 1)))))
             (append (flatten* (cdr lst) depth)
                     re)))
    (t (cons (car lst)
             (append (flatten* (cdr lst) depth) re)))))