StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><code>(apply (function append) (mapcar #'g ...))</code> is just <a href="http://www.lispworks.com/documentation/HyperSpec/Body/f_mapc_.htm" rel="nofollow noreferrer"><code>mapcan</code></a> (<strong>update:</strong> <a href="https://stackoverflow.com/questions/20207041/why-does-this-mapcan-cause-my-repl-to-freeze"><em>with usual caveats</em></a> about destructive update and quoted lists, see also <a href="https://stackoverflow.com/questions/9946612/how-to-use-mapcar-here/9949958#9949958">this</a>):</p> <pre><code>(defun describe-paths (location edges) (mapcan #'describe-path (cdr (assoc location edges)))) </code></pre> <p>Recursion is good for thinking, for understanding. But actually using it in your code comes with a price.</p> <p>Your recursive re-write is <a href="https://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons" rel="nofollow noreferrer">tail recursive modulo cons</a>; no Lisp has this optimization AFAIK, even though <a href="http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR19" rel="nofollow noreferrer">it was first described in 1974</a>, <em>in Lisp</em>.</p> <p>So what you wrote is good as an <em>executable specification</em>.</p> <p>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).</p> <p>Common Lisp, being a practical language, would have us just write the loop out directly. For one,</p> <pre><code>(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)))) </code></pre> <p>is guaranteed to work in constant stack space. </p> <p><sup><strong>update:</strong> this destructively concatenates lists returned by <em><code>describe-path</code></em> so it should take care not to return lists with the same <code>last</code> cons cell on separate invocations, or this could create circular structure. Alternatively, the call to <code>describe-path</code> could be wrapped in a <code>copy-list</code> call. Of course, if <code>describe-path</code> were to return a list which is already cyclic, <code>last</code> here would go into a loop too.</sup></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload