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" ?

Answer 1

(apply (function append) (mapcar #'g ...)) is just mapcan (update: with usual caveats about destructive update and quoted lists, see also this):

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

Recursion is good for thinking, for understanding. But actually using it in your code comes with a price.

Your recursive re-write is tail recursive modulo cons; no Lisp has this optimization AFAIK, even though it was first described in 1974, in Lisp.

So what you wrote is good as an executable specification.

But Common Lisp is a practical language. In particular, it has many ways to encode iteration. Remember, iterative processes are our goal; recursive processes are terrible, efficiency-wise. So when we write a code which is syntactically recursive, we still want it to describe an iterative process (such that runs in constant stack space).

Common Lisp, being a practical language, would have us just write the loop out directly. For one,

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

is guaranteed to work in constant stack space.

^{update: this destructively concatenates lists returned by describe-path so it should take care not to return lists with the same last cons cell on separate invocations, or this could create circular structure. Alternatively, the call to describe-path could be wrapped in a copy-list call. Of course, if describe-path were to return a list which is already cyclic, last here would go into a loop too.}

Answer 2

I saw several opinions about using apply is a bad style. But actually that would be great if somebody will explain me why apply is considered to be bad.

What do you mean using a word "lispy". Common lisp allows to program in any style you want.

If "lispy" means functional programming style, then the first code is written in more functional programming style. A function is passed to a function mapcar and another function is passed to apply and all the job is done by passing the results of one function to another. In you code you don't pass functions as arguments to other functions. But recursion can be considered as functional programming style sign. And code in the book is shorter than yours.

If you don't like apply because of apply determines the argument count in runtime, you can use reduce in this situation (if I understood the data structures correctly): (Thanks to Joshua Taylor for pointing a huge resource overhead without :from-end t key argument)

(defun describe-paths (location edges)
  (reduce #'append (mapcar #'describe-path
            (rest (assoc location edges))) :from-end t))

Anyway I'm pretty sure that the purpose of the code in the book is the education reason. It's an example of mapcar and apply that shows how lists are treated as data and code in lisp.

p.s. Actually I figured why apply can be bad (stack is used for function calls).

> (apply #'+ (make-list 500000 :initial-element 1))
*** - Lisp stack overflow. RESET

So as Rainer Joswig told it's lispy to avoid stack overflows. Reduce fix the problem.

> (reduce #'+ (make-list 50000000 :initial-element 1))
50000000