Creating repetitions of list with mapcan freezes?

Question

I have two lists: (1 2 3) and (a b) and I need to create something like this (1 2 3 1 2 3). The result is a concatenation of the first list as many times as there are elements in the second. I should use some of the functions (maplist/mapcar/mapcon, etc.). This is exactly what I need, although I need to pass first list as argument:

(mapcan #'(lambda (x) (list 1 2 3)) (list 'a 'b))
;=> (1 2 3 1 2 3)

When I try to abstract it into a function, though, Allegro freezes:

(defun foo (a b)
  (mapcan #'(lambda (x) a) b))

(foo (list 1 2 3) (list 'a 'b))
; <freeze>

Why doesn't this definition work?

Answer 1

You could

(defun f (lst1 lst2)
  (reduce #'append (mapcar (lambda (e) lst1) lst2)))

then

? (f '(1 2 3) '(a b))
(1 2 3 1 2 3)

Answer 2

There's already an accepted answer, but I think some more explanation about what's going wrong in the original code is in order. mapcan applies a function to each element of a list to generate a bunch of lists which are destructively concatenated together. If you destructively concatenate a list with itself, you get a circular list. E.g.,

(let ((x (list 1 2 3)))
  (nconc x x))
;=> (1 2 3 1 2 3 1 2 3 ...)

Now, if you have more concatenations than one, you can't finish, because to concatenate something to the end of a list requires walking to the end of the list. So

(let ((x (list 1 2 3)))
  (nconc (nconc x x) x))
;        -----------      (a)
; ---------------------   (b)

(a) terminates, and returns the list (1 2 3 1 2 3 1 2 3 ...), but (b) can't terminate since we can't get to the end of (1 2 3 1 2 3 ...) in order to add things to the end.

Now that leaves the question of why

(defun foo (a b)
  (mapcan #'(lambda (x) a) b))

(foo (list 1 2 3) '(a b))

leads to a freeze. Since there are only two elements in (a b), this amounts to:

(let ((x (list 1 2 3)))
  (nconc x x))

That should terminate and return an infinite list (1 2 3 1 2 3 1 2 3 ...). In fact, it does. The problem is that printing that list in the REPL will hang. For instance, in SBCL:

CL-USER> (let ((x (list 1 2 3)))
           (nconc x x))
; <I manually stopped this, because it hung.

CL-USER> (let ((x (list 1 2 3)))
           (nconc x x)            ; terminates
           nil)                   ; return nil, which is easy to print
NIL

If you set *print-circle* to true, you can see the result from the first form, though:

CL-USER> (setf *print-circle* t)
T
CL-USER> (let ((x (list 1 2 3)))
           (nconc x x))
#1=(1 2 3 . #1#)                  ; special notation for reading and
                                  ; writing circular structures

The simplest way (i.e., fewest number of changes) to adjust your code to remove the problematic behavior is to use copy-list in the lambda function:

(defun foo (a b)
  (mapcan #'(lambda (x)
              (copy-list a))
          b))

This also has an advantage over a (reduce 'append (mapcar ...) :from-end t) solution in that it doesn't necessarily allocate an intermediate list of results.

Answer 3

Rule of thumb is to make sure the function supplied to mapcan (and destructive friends) creates the list or else you'll make a loop. The same applies to arguments supplied to other destructive functions. Usually it's best if the function has made them which makes it only a linear update.

This will work:

(defun foo (a b)
  (mapcan #'(lambda (x) (copy-list a)) b))

Here is some alternatives:

(defun foo (a b)
  ;; NB! apply sets restrictions on the length of b. Stack might blow
  (apply #'append (mapcar #'(lambda (x) a) b)) 

(defun foo (a b)
   ;; uses loop macro
   (loop for i in b
         append a))

I really don't understand why b cannot be a number? You're really using it as church numbers so I think I would have done this instead:

(defun x (list multiplier)
   ;; uses loop
   (loop for i from 1 to multiplier
         append list))

(x '(a b c) 0) ; ==> nil
(x '(a b c) 1) ; ==> (a b c)
(x '(a b c) 2) ; ==> (a b c a b c)

;; you can still do the same:
(x '(1 2 3) (length '(a b))) ; ==> (1 2 3 1 2 3)