Common Lisp中的高效收集功能

Question

我正在学习Lisp并编写了以下函数来收集结果列表.

(defun collect (func args num)
  (if (= 0 num)
      ()
      (cons (apply func args)
        (collect func args (- num 1)))))

它产生了与内置循环函数类似的输出.

CL-USER> (collect #'random '(5) 10)
(4 0 3 0 1 4 2 1 0 0)
CL-USER> (loop repeat 10 collect (random 5))
(3 3 4 0 3 2 4 0 0 0)

但是当我尝试生成一个100,000个元素的列表时,我的collect函数会打击堆栈

CL-USER> (length (collect #'random '(5) 100000))
Control stack guard page temporarily disabled: proceed with caution

而循环版本没有

CL-USER> (length (loop repeat 100000 collect (random 5)))
100000

如何让我的版本更节省空间,是否有其他方法可供选择？我认为这是尾递归.我正在使用sbcl.任何帮助都会很棒.

Answer 1

不,它不是尾递归.ANSI Common Lisp都没有说明它和你的代码:

(defun collect (func args num)
  (if (= 0 num)
      ()
      (cons (apply func args)
            (collect func args (- num 1)))))

如果你查看你的代码,那么你对COLLECT的调用会有一个CONS.这个CONS接收到COLLECT的递归调用的值.因此COLLECT不能是尾递归.通过引入累加器变量将函数重写为看起来是尾递归的东西是相对简单的.各种Lisp或Scheme文献应该描述这一点.

在Common Lisp中,编程迭代计算的默认方法是使用以下几种迭代结构之一:DO,DOTIMES,DOLIST,LOOP,MAP,MAPCAR,......

Common Lisp标准不提供尾调用优化(TCO).必须指明TCO在存在其他几种语言功能时应该做什么.例如,动态绑定和特殊变量会影响TCO.但是,Common Lisp标准一般都没有说明TCO和TCO的可能影响.TCO不是ANSI Common Lisp标准的一部分.

几个Common Lisp实现有一种方法可以使用编译器开关启用各种尾调用优化.请注意,启用它们的方式和限制都是特定于实现的.

简介:在Common Lisp中使用迭代构造而不是递归.

(defun collect (func args num)
  (loop repeat num
        collect (apply #'func args)))

额外奖励:它更容易阅读.

Answer 2

ANSI标准不要求Common Lisp实现进行尾调用优化; 然而,大多数值得他们的盐(包括SBCL)都做了优化.

另一方面,您的函数不是尾递归.它可以通过引入一个额外的参数来累积中间结果的常见技巧变成一个:

    (defun collect (func args num)
      (labels ((frob (n acc)
                 (if (= 0 n)
                     acc
                     (frob (1- n) (cons (apply func args) acc)))))
        (frob num nil)))

(原始参数FUNC和ARGS在本地函数中被消除,因为它们是恒定的并且需要注意它).