Rewrite apply function to use recursion instead

Question

Probably the hardest part of learning lisp has been to think in the "lisp way" which is elegant and impressive, but not always easy. I know that recursion is used to solve a lot of problems, and I am working through a book that instead uses apply to solve a lot of problems, which I understand is not as lispy, and also not as portable.

An experienced lisper should be able to help with this logic without knowing specifically what describe-path, location, and edges refer to. Here is an example in a book I am working through:

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

I have successfully rewritten this to avoid apply and use recursion instead. It seems to be working:

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

I would like some more seasoned pairs of eyes on this to advise if there is a more elegant way to translate the apply to recursion, or if I have done something unwise. This code seems decent, but would there been something even more "lispy" ?

• JustAnotherCurious: why do you think using apply is a bad style? I saw several similar opinions, but didn't get any arguments for that.
• Joshua Taylor: Using apply isn't non-Lispy, but using (apply function ...) can be an issue if you don't know how big the list can be.
• Joshua Taylor: Cross posted on StackOverflow stackoverflow.com/q/20188008/1281433.

Answer 1

Lisp is a multiparadigm language.

apply is just as lispy as recursion, and, in a way, much more so (think in HOFs)!

Style

1. Please fix indentation.

2. Please write #'foo instead of (function foo).

Implementations

The first (HOF) version can be much more efficiently rewritten in using mapcan (provided defscribe-path returns fresh lists):

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

The second (recursive) version can be made tail recursive using an accumulator. This would help some compilers produce better code.

(defun describe-paths-recursive (location edges)
 (labels ((processx-edge (edge acc)
 (if (null edge)
 acc
 (processx-edge (rest edge) 
 (revappend acc (describe-path (first edge)))))))
 (nreverse (processx-edge (cdr (assoc location edges))))))

Note the use of revappend/nreverse instead of append to avoid quadraticity.

• johnbakers: is the accumulator a requirement for tail recursion optimization, or just a hint that could potentially be ignored?
• sds: I don't think you can avoid an accumulator if you write a tail recursive version, but you can try (or maybe I did not understand your question)