Search code examples
lispcommon-lisp

Does `mapcan` really use `nconc`?


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?


Solution

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