1

我正在阅读 Paul Graham 的《On Lisp》一书。在第 4 章“实用函数”中，他给出了对列表进行操作的小函数的示例，这对编写较大的程序很有帮助。

其中之一是flatten。给定任意级别的嵌套列表作为参数，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)。

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

4

3 回答 3

3

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

也许 a(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))))
于 2014-09-16T10:42:00.490 回答
3

你实际上非常接近。正如 Sylwester 提到的，问题在于(push el acc)仅修改el的本地绑定（其中每次调用rflatten都会有一个新绑定。正如 Rainer 提到的，它并不是传统意义上的累加器，所以我m 不会将其称为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变量来绑定result，所以

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

接下来是dolist可以接受第三个参数，一种用于评估返回值的形式。这通常用于“推送创建列表，然后反向获取返回值”成语，例如，

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

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

(defun flatten (lst &aux (result '()))
  (labels ((rflatten (lst1)
             (dolist (el lst1 result)
               (if (listp el)
                 (rflatten el)
                 (push el result)))))
      (nreverse (rflatten lst))))
于 2014-09-16T10:58:28.777 回答
1

cons由es构建结果的非递归代码，遵循注释并从user: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))

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

于 2018-02-21T03:34:02.290 回答