重写apply函数以改为使用递归

Question

学习口齿不清的最困难的部分可能就是以"优质的方式"进行思考,这种方式既优雅又令人印象深刻,但并不总是那么容易.我知道递归用于解决很多问题,我正在编写一本书,而不是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(更新: 与常规注意事项有关破坏性更新,并引述名单,参见本):

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

递归有利于思考,理解.但实际上在你的代码中使用它需要付出代价.

你的递归重写是尾递归的模数 ; 没有Lisp有这种优化AFAIK,即使它最初是在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))))

保证在恒定的堆栈空间中工作.

^{update:这会破坏性地连接返回的列表,describe-path所以它应该注意不要last在单独的调用中返回具有相同cons单元的列表,否则这可能会创建循环结构.或者,describe-path可以将copy-list呼叫包裹在呼叫中.当然,如果describe-path要返回一个已经循环的列表,last这里也会进入循环.}