lisp - 重写应用函数以使用递归代替

Question

学习 lisp 最困难的部分可能是用“lisp 方式”思考，这种方式优雅而令人印象深刻，但并不总是那么容易。我知道递归用于解决很多问题，我正在阅读一本书，而不是使用 apply 来解决很多问题，我理解它不像 lispy，也不像可移植。

有经验的 lisper 应该能够在不知道 describe-path location 和 edges 具体指的是什么的情况下帮助处理这个逻辑。这是我正在阅读的一本书中的示例:

(defun describe-paths (location edges)
  (apply (function append) (mapcar #'describe-path
               (cdr (assoc location edges)))))

我已经成功地重写了它以避免 apply 并改用递归。它似乎在工作:

(defun describe-paths-recursive (location edges)
  (labels ((processx-edge (edge)
         (if (null edge)
         nil
         (append (describe-path (first edge))
             (processx-edge (rest edge))))))
    (processx-edge (cdr (assoc location edges)))))

如果有更优雅的方法将 apply 转换为递归，我希望有更多经验丰富的人提出建议，或者我是否做了一些不明智的事情。这段代码看起来还不错，但还会有更“lispy”的东西吗？

Answer 1

(apply (function append) (mapcar #'g ...)) 只是 mapcan (更新: with usual caveats 关于破坏性更新和引用列表，另见 this ):

(defun describe-paths (location edges)
  (mapcan #'describe-path
               (cdr (assoc location edges))))

递归有利于思考和理解。但实际上在您的代码中使用它是有代价的。

您的递归重写是 tail recursive modulo cons ;没有 Lisp 有这种优化 AFAIK，即使 it was first described in 1974 , 在 Lisp 中。

所以你写的是可执行规范。

但是 Common Lisp 是一种实用的语言。特别是，它有很多编码迭代的方法。请记住，迭代过程是我们的目标；递归过程在效率方面很糟糕。因此，当我们编写语法递归的代码时，我们仍然希望它描述一个迭代过程(这样在常量堆栈空间中运行)。

Common Lisp 是一种实用的语言，它会让我们直接将循环写出来。一方面，

(defun describe-paths-loop (location edges &aux (res (list 1)) (p res))
  (dolist (x (cdr (assoc location edges)) 
             (cdr res))                   ; the return form
    (setf (cdr p) (describe-path x))
    (setf p (last p))))

保证在常量堆栈空间中工作。

^{更新:这会破坏性地连接 describe-path 返回的列表，因此应该注意不要返回具有相同路径的列表last 在单独的调用中使用 cons 单元格，否则这可能会创建循环结构。或者，可以将对 describe-path 的调用包装在 copy-list 调用中。当然，如果 describe-path 返回一个已经循环的列表，这里的 last 也会进入循环。}