Why does this mapcan cause my REPL to freeze?

Question

In this very useful answer, it was suggested I could replace this code:

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

With this:

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

I certainly understand conceptually why this should work, but it doesn't; the second variation freezes my REPL and the CL prompt never returns. I have to restart SLIME. So I looked it up, and am wondering if the fact that mapcan doesn't use list, but rather nconc, is the cause? Therefore these are actually not identically functioning code blocks?

For the curious, I am passing this:

(describe-paths-mapcan 'living-room *edges*)

Where *edges* is:

(defparameter *edges* '((living-room (garden west door)
             (attic upstairs ladder))
            (garden (living-room east door))
            (attic (living-room downstairs ladder))))

And:

(defun describe-path (edge)
  `(there is a ,(caddr edge) going ,(cadr edge) from here.))

@DaoWen initially, but I'm experimenting with other ways to write the examples in that book, so I can learn the language better — johnbakers

Sylwester Sylwester · Accepted Answer · 2013-11-26T02:09:22

I think it has to do with describe-edges. It is defined as:

(defun describe-path (edge)
  `(there is a ,(caddr edge) going ,(cadr edge) from here.))

The quasiquote there we can macroexpand.. And you get:

(macroexpand '`(there is a ,(caddr edge) going ,(cadr edge) from here.)) ; ==>
(CONS 'THERE
 (CONS 'IS
  (CONS 'A
   (CONS (CADDR EDGE) (CONS 'GOING (CONS (CADR EDGE) '(FROM HERE.)))))))

According to the documentation for mapcan the concatination is done destructively. Looking at the very last element of whats returned from describe-path will share structure with the next element it returns so nconc will make an infinite loop.

If you were to change describe-edges to the following it will work:

(defun describe-path (edge)
  (list 'there 'is 'a (caddr edge) 'going (cadr edge) 'from 'here.))

Why does this mapcan cause my REPL to freeze?

1 Answers