Search code examples
lispcommon-lisp

Question regarding mapcon and its supposed equivalence to (apply #'nconc (maplist ...))

The Hyperspec states that mapcon is (roughly?) equivalent to (apply #'nconc (maplist ...)), i.e. "the results of applying function are combined into a list by the use of nconc rather than list".

But if this

(maplist #'identity '(1 2 3)) ; '((1 2 3) (2 3) (3))
(apply #'nconc '((1 2 3) (2 3) (3)))

works, why doesn't this

(apply #'nconc (maplist #'identity '(1 2 3)))
(mapcon #'identity '(1 2 3))

work also?

Solution

  • Bearing in mind that examples are not part of the specification, the relationship is defined as:

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

    Also, NCONC is defined recursively in terms of LAST and RPLACD:

    (nconc) =>  ()
(nconc nil . lists) ==  (nconc . lists)
(nconc list) =>  list
(nconc list-1 list-2) ==  (progn (rplacd (last list-1) list-2) list-1)
(nconc list-1 list-2 . lists) ==  (nconc (nconc list-1 list-2) . lists)

    An implementation is free to have an efficient implementation for this, provided it computes the same result. But, since it is defined to use rplacd, it definitely mutates the list (it links the cdr slot of each intermediate result's last cons cell).

    Section §3.7.1 Modification of Literal Objects also says that:

    The consequences are undefined if literal objects are destructively modified.

    In your case, you are calling #'identity and concatenating destructively values which comes from a quoted list, ie. literal data. The behavior is undefined.

    Using freshly allocated lists

    If, instead of identity you call copy-list, then each intermediate result is a fresh list and the result is defined:

    (equalp (apply #'nconc (maplist #'copy-list '(1 2 3)))
        (mapcon #'copy-list '(1 2 3)))
=> T

    Accidental circular lists

    If you use non-literal data like (list 1 2 3) the behavior is still undefined, but this is more subtle. For example, let's print the result of (maplist #'identity (list 1 2 3)) while taking care of circularity:

    (write (maplist #'identity (list 1 2 3)) :circle t)

    This prints the following, with #n= being labels (reader variables) and #n# back-references to the same lists as previously labeled:

    ((1 . #1=(2 . #2=(3))) #1# #2#)

    In other words, the result is a list of three lists (L1 L2 L3), where L2 is the rest of L1 and L3 the rest of L2. This means that if you do:

    (apply #'nconc (maplist #'identity (list 1 2 3)))

    It is as-if you did:

    (let* ((L1 (list 1 2 3))
       (L2 (rest L1))
       (L3 (rest L2)))
  (nconc L1 L2 L3))

    Given the above recursive definition, it is equivalent to:

    (nconc (nconc L1 L2) L3)
^      ^
|      |
|      \-- inner nconc (N1)
|
\-- outer nconc (N0)

    The inner term N1 is itself evaluated as:

    (progn (rplacd (last L1) L2) L1)

    Here, the end of L1 is linked to L2 (the rest of L1), which creates a loop. You can try it directly and your environment should print it elided; for example in SBCL:

    * (setf *print-length* 10)
10

* (let ((L1 (list 1 2 3)))
    (nconc L1 (rest L1)))
(1 2 3 2 3 2 3 2 3 2 ...)

    You could also print it to the REPL by setting *print-circle* to T.

    That in itself is fine, but then this infinite list is used in the outer invocation of nconc named N0 above. Let's say the intermediate result of evaluating N1 is R1:

    (nconc R1 L3)

    The above is evaluated as:

    (progn (rplacd (last R1) L3) R1)

    And here the program is stuck, because last never terminates.

    At least, this is the case in most implementations, but note that LAST is defined only when the list is not circular:

    list---a list, which might be a dotted list but must not be a circular list.

    That's why the behavior is actually undefined here.