Rewrite apply function to use recursion instead

Question

Probably the hardest part of learning lisp was thinking of “lisp,” which is sleek and impressive, but not always easy. I know that recursion is used to solve many problems, and I am working on a book that instead uses apply to solve many problems, which, as I understand it, are not so deprived and also not portable.

An experienced specialist should be able to cope with this logic, not knowing specifically what describe-path location and edges . Here is an example in a book I'm working on:

 (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 work:

 (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 experienced pair of eyes on this to advise if there is a more elegant way to translate apply into recursion, or if I did something unreasonable. This code seems decent, but was there anything even more "slimy"?

Answer 1

There is nothing wrong with this matter; for example, the python category asks a lot of questions like this.

But to your question: what are you doing is good. In fact, it is almost similar, almost identical, to the more general technique that Peter Norwig shows in one of his Lisp books, so either you read this book or you came across good practice. In any case, this is a perfectly acceptable recursion implementation.

Answer 2

(apply (function append) (mapcar #'g ...)) just mapcan ( update: with the usual caveats about destructive updating and cited 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 its use in the code has a price.

Your recursive rewrite tail recursive modulos cons ; no Lisp has this AFAIK optimization, although 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 iteration coding methods. Remember that iterative processes are our goal; recursive processes are terrible, efficient. Therefore, when we write code that is syntactically recursive, we still want it to describe an iterative process (one that works in a constant stack space).

A common Lisp, which is a practical language, would make us just write a loop 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)))) 

guaranteed to work in a constant stack space.

^{update:, this destroys the concatenation of the lists returned by describe-path , so care should be taken not to return lists with the same last cons cell to individual calls, or this could create a circular composition. Alternatively, the call to describe-path can be completed by calling copy-list . Of course, if describe-path was supposed to return a list that is already circular, last also falls into the loop here.}

Answer 3

I saw some opinions about using apply - this is a bad style. But actually it would be great if someone explains to me why apply is considered bad.

What do you mean by lispy. Common lisp allows you to program any style.

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

If you don't like apply because apply determines the number of arguments at run time, you can use reduce in this situation (if I understood the data structures correctly): (Thanks to Joshua Taylor for pointing out the huge overhead of the resource without an argument :from-end t )

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

In any case, I am sure that the purpose of the code in the book is the reason for education. This is an example of mapcar and apply , which shows how lists are treated as data and code in lisp.

ps Actually, I understood why apply can be bad (the stack is used for function calls).

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

Since Rainer Joswig said he is deprived to avoid. Reduce the fix for the problem.

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

Answer 4

The Lisp way is to use functional, imperative, or object-oriented programming (with or without a changed state) to solve a problem or come up with some other programming as you see fit and express it in macros. Finding recursion while ignoring other approaches is not a Lisp way; this is the way of the wayward Lisp academic.

The easiest way to rewrite a function:

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

- use loop . The correct motivation for elimination is that we expect many paths that can exceed the limit of the number of function arguments.

Everything you do with apply makes a large list of arguments to the append function. We can add any number of lists to a large list using loop as follows:

 (defun describe-paths (location edges) (loop for path in (cdr (assoc location edges)) appending (describe-path path)) 

Presumably, describe-path returns a list, and you want to link them together.

The appending loop appending , which can also be written by append , collects adds the value of the argument form to the anonymous list. This list becomes the return value when the loop ends.

We can use nconcing to improve performance if we have reason to believe that the lists returned by described-path are just assigned to each call.