lisp - 使用 mapcan 卡住创建列表的重复？

Question

我有两个列表:(1 2 3) 和 (a b) 我需要创建这样的列表 (1 2 3 1 2 3) 。结果是第一个列表的串联次数与第二个列表中的元素数一样多。我应该使用一些功能(maplist/mapcar/mapcon 等)。这正是我所需要的，尽管我需要将第一个列表作为参数传递:

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

但是，当我尝试将其抽象为一个函数时，Allegro 卡住了:

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

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

为什么这个定义不起作用？

Answer 1

已经有一个公认的答案，但我认为需要对原始代码中出现的问题进行更多解释。 mapcan 将函数应用于列表的每个元素以生成一堆列表，这些列表被破坏性地连接在一起。如果你破坏性地将一个列表与其自身连接起来，你会得到一个循环列表。例如，

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

现在，如果您的连接数多于一个，则无法完成，因为将某些内容连接到列表末尾需要走到列表末尾。所以

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

(a) 终止，并返回列表 (1 2 3 1 2 3 1 2 3 ...)，但 (b) 无法终止，因为我们无法到达(1 2 3 1 2 3 ...) 的结尾，以便将内容添加到结尾。

现在剩下的问题是为什么

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

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

导致卡住。由于 (a b) 中只有两个元素，这相当于:

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

那应该终止并返回一个无限列表 (1 2 3 1 2 3 1 2 3 ...)。事实上，确实如此。问题是 打印 REPL 中的列表将会挂起。例如，在 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

如果将 *print-circle* 设置为 true，您可以看到第一种形式的结果:

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

调整代码以消除问题行为的最简单方法(即，最少的更改)是在 lambda 函数中使用 copy-list:

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

这也优于 (reduce 'append (mapcar ...) :from-end t) 解决方案，因为它不一定分配结果的中间列表。