Does mapcan in common lisp change the value of argument?

Yes, MAPCAN can change the value of its argument. To see why this is, I'll try to give an explanation for what it's useful for, and for the optimisation which has been done to cause this. (Note: I assume you understand the problems with modifying quoted objects: my examples avoid these by freshly consing everything.)

First of all, consider MAPCAR: what this does is map a function over a list, constructing a new list for which each element is the result of the function applied to the corresponding element of the original list. That's great if that's what you want to do: but what if you wanted, for instance, to produce a result with several elements for each element in the original list, where 'several' might mean 'none'. For instance, you might want to write some function which filters a list to produce only the elements of it which are numbers.

Well, a natural way to do that is to expect that the function you are mapping would produce a list of results, and then the mapping function would take these lists and append them together. This is what MAPCAN does. Here are two examples of how it can be used 'properly'. First of all here's a function which filters a list for entries which are numbers:

(defun numbers-of (l)
  (mapcan (lambda (e)
            (if (numberp e) (list e)
              '()))
          l))

And now

> (numbers-of '(1 2 3 4 a () b (1) 9))
(1 2 3 4 9)

(This function can very easily be generalised to create a general filter, obviously.)

Secondly here is a function which takes an association list and returns a property list, by returning a two-element list for each cons in the original alist:

(defun plistify (alist)
  (mapcan (lambda (e)
            (list (car e) (cdr e)))
          alist))

And

> (plistify '((a . 1) (b . 2)))
(a 1 b 2)

So that's all easy to understand.

But there's a thing to notice here: in both of these functions the bit of list structure that the function being mapped returns is completely ephemeral: its only purpose in life is to tell MAPCAN how many elements you want in the resulting list. Also remember that it's 1960: the machine you want to run this on can execute a few thousand instructions a second and has a few thousand words of memory. A garbage collection means you can go and make a cup of tea: the whole notion of ephemeral consing being free, which isn't really true now, definitely was not true then.

So there's a trick you can do: instead of constructing a new list of the results, you destructively modify, with NCONC, the lists that the mapped function is giving you. This means that MAPCAN conses no more than the function being mapped conses (which is less than MAPCAR conses!).

This is a brilliant trick, but it has a downside: the list structure returned by the mapped function is destructively modified, so if that structure is not fresh then anything else that refers to it is destructively modified as well. So in your example, you are mapping CDR, and it is returning structure which shares with parts of the original list. And this those parts are being modified as well. So you can get quite surprising results:

> (let ((a (loop repeat 10 collect (list 1 1))))
    (values (mapcan #'cdr a) a))
(1 1 1 1 1 1 1 1 1 1)
((1 1 1 1 1 1 1 1 1 1 1)
 (1 1 1 1 1 1 1 1 1 1)
 (1 1 1 1 1 1 1 1 1)
 (1 1 1 1 1 1 1 1)
 (1 1 1 1 1 1 1)
 (1 1 1 1 1 1)
 (1 1 1 1 1)
 (1 1 1 1)
 (1 1 1)
 (1 1))

This constructs a list with ten (distinct) sublists of two elements and then maps CDR over it with MAPCAN, returning the result and the (modified) original list. The result is reasonably surprising! It helps if you ask the system to show you shared structure:

> (let ((*print-circle* t)
        (a (loop repeat 10 collect (list 1 1))))
    (pprint (mapcan #'cdr a))
    (pprint a))

(1 1 1 1 1 1 1 1 1 1)
((1
  1
  . #1=(1
        . #2=(1
              . #3=(1
                    . #4=(1
                          . #5=(1
                                . #6=(1 . #7=(1 . #8=(1 . #9=(1))))))))))
 (1 . #1#)
 (1 . #2#)
 (1 . #3#)
 (1 . #4#)
 (1 . #5#)
 (1 . #6#)
 (1 . #7#)
 (1 . #8#)
 (1 . #9#))

Well: it doesn't help in terms of 'getting pretty output', but you can see all the sharing that is going on: there are not as many conses here as it looks.

So MAPCAN is great in two cases:

• if you make sure that the list you return is freshly-consed;
• if you understand what it does, don't cons fresh structure, and somehow make use of the side-effects.

I don't think I have done the second thing, but I bet other people have.

I am fairly sure that, if Lisp was being invented today (which, of course, it is), MAPCAN would either not be there or be in some low-level library: instead there'd be a function like Alexandria's MAPPEND, as mentioned in a comment. But I think, in fact, MAPCAN has its uses.

For additional fun, try to predict the result of these two, apparently similar, calls. You will want to bind either or both *PRINT-LENGTH* and *PRINT-CIRCLE* to values which stop the system running away (and know how to interrupt your Lisp).

Example 1:

(let* ((e (list 1 1))
       (l (list e e)))
  (mapcan #'cdr l))

Example 2:

(let* ((e (list 1 1))
       (l (list e e e)))
  (mapcan #'cdr l))

I am not at all sure that the behaviour of either of these examples is well-defined.

Mapcan is "destructive", applying the destructive 'nconc to the intermediate mapping result.

If we break it down, mapping with CDR first yielded:

(b) nil (2 3)

But that is not new structure. For example, the cons cell forming (b) is identical to the second cons cell in (a b). If you cannot mentally imagine the second cons cell, we can eschew the Lisp syntactic sugar and write it this way:

(a . (b . nil))

Returning to our intermediate results...:

(b . nil) nil (2 . (3 . nil))

...when we ask mapcan to combine those and it eventually changes the cdr of (b . nil) to (2 . (3 . nil)), it is also replacing the CDR of (a . (b . nil)) because it is the same CDR! Scary, right? This is why one wants to think a bit when using destructive operations (and why we call them "destructive").

Now for fun, try this:

(setf (caddar x) 42)

Now evaluate x.

ps. Watch out also for destructive operations on quoted lists. For my experimentation I used:

(defparameter abc (copy-list '((a b) (c) (1 2 3))))
(defparameter ab (mapcan #'cdr abc))
(print ab)
(print abc)
(setf (caddar abc) 42)
(print abc)