Does `mapcan` really use `nconc`?

Question

According to Common Lisp HyperSpec (CLHS), mapcan uses nconc to combine its results into a list. CLHS also says that

(mapcon f x1 ... xn)
   ==  (apply #'nconc (maplist f x1 ... xn))

So I've been concerned about the ramifications of using apply where call-arguments-limit is low - CLHS says it can be as low as 50, and on LispWorks it's 2047. On LispWorks,

(mapcan #'list (loop for i from 0 to call-arguments-limit collect i))

succeeds, while

(apply #'nconc (mapcar #'list (loop for i from 0 to call-arguments-limit collect i)))

fails. If mapcan really has to use nconc, shouldn't both of these fail?

Barbosa

I don't read that as "this function must be implemented this way", so much as "this function must behave equivalently to this code". I'm sure mapcan is more efficient than a straight apply; the nconc comment is merely to show the difference between mapcan and the other list functions. – Voltaic

Answer 1

An important point of the specification is 1.4.3 Sections Not Formally Part Of This Standard, which says in particular that examples are provided for illustration only and not part of the standard.

Generally in the HyperSpec, examples that show how to express one construct with another are intended to show the intent of the function, and may assume the example works on some abstract implementation that has no physical restrictions like memory etc.

There is not requirement that MAPCAN or MAPCON uses NCONC in the exact way shown here, and in fact I don't think there is a formal definition of what == means (technically the code also uses an ellipsis so it is not written in Common Lisp).

A better example would have been to use REDUCE to NCONC the consecutive results, or even a LOOP. I think the use of APPLY in this example is unfortunate but ultimately you can assume that neither MAPCON nor MAPCAN are restricted by CALL-ARGUMENTS-LIMIT.

For example, you could express it as follows, but the actual MAPCAN might not need to allocate the intermediate list as done by MAPCAR, it could just fuse both operations:

(reduce #'nconc (mapcar f x1 .. xn))

Mohandas

Answer 2

Quoting from the standard:

mapcan and mapcon are like mapcarand maplist respectively, except that the results of applying function are combined into a list by the use of nconc rather than list.

So, does that mean mapcar must be implemented by (apply #'list ...)? Don't be silly, of course it need not be. What it means is that the results from the function called by mapcar are combined into a list in the same way list does that: by building a chain of cons cells whose cars point to the returned values.

In exactly the same way, the results returned from the function called by mapcan are combined in the way that nconc does, namely that they must be lists and these lists are concatenated destructively.

That is what the language in the standard means.

As an example here is an implementation of a simple version (only one list argument) of mapcan which does use nconc to build the list, but only ever calls nconc with two arguments. This is not how you would implement mapcan in real life, but it is simple enough that you can see what is going on without relying on reduce.

(defun mc (f l)
  (labels ((mc-loop (tail head last)
             ;; tail is the rest of the list we're processing, head is
             ;; the thing we are building, last is the last non-null
             ;; return from f if there is one
             (if (null tail)            ;we're done
                 head
               (let ((r (funcall f (first tail))))
                 (mc-loop (rest tail)
                          (if (null head) r head) ;the first non-null return is the head
                          (if (null r)
                              ;; last non-null element is unchanged
                              last
                            (progn
                              ;; smash last and then r is the new last
                              (nconc last r)
                              r)))))))
    (mc-loop l '() '())))

Caladium