使用普通 lisp 展平列表 [英] Flatten a list using common lisp

问题描述

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

I was reading the book On Lisp by Paul Graham. In Chapter 4, Utility Functions, he gives examples of small functions that operate on lists, which would be helpful while writing a larger program.

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

One of them is flatten. Given a nested list at any arbitrary level as argument, flatten will remove all the nested elements and put them on the top level.

以下是我实现扁平化的尝试:

Below is my attempt at implementing 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))))

但是上面的函数没有正确地展平列表.

But the above function does not flatten lists properly.

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

使用(1 (2)) 调用函数返回(1) 而不是(1 2).

Calling the function with (1 (2)) returns (1) instead of (1 2).

我找不到我的 flatten 实现有什么问题.这是我使用的方式吗标签?还是我使用 dolist 宏的方式?dolist 宏总是返回 nil.但这并不重要，因为我使用累加器 acc 来存储扁平列表.

I cannot find what's wrong with my implementation of flatten. Is it the way I am using labels? Or is it the the way I am using the dolist macro? The dolist macro always returns nil. But that should not matter as I am using an accumulator acc to store the flattened list.

推荐答案

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

push changes the symbol binding in scope. Thus the recursion (rflatten el acc) has it's own acc which is the result there but you don't do anything with the returned result and it doesn't alter the callee acc.

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

Perhaps a (setf acc (rflatten el acc)) would fix that:

(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))))

这篇关于使用普通 lisp 展平列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！