使用通用Lisp拼合列表 [英] Flatten a list using common lisp

问题描述

我正在阅读保罗·格雷厄姆(Paul Graham)的《关于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出了什么问题.这是我使用的方式吗 labels?还是我使用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))可以解决此问题:

(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屋！