lisp - 将列表中的每个项目加倍，同时限制 Lisp 中的 cons 调用

Question

我有一个函数可以将列表中的每一项加倍:

(defun double (L)
   (cond
      ((atom L) nil)
      (t (cons (car L) (cons (car L ) (double (cdr L))))) ) )

(double '(a b c )) => (a a b b c c)

如何将函数调用 cons 的次数除以 2 来获得相同的结果？ (即在前面的示例中，它调用了 6 次 cons。我怎么可能只调用 3 次呢？)

谢谢!

编辑 2，在 jkiiski 的评论之后，似乎现在可以工作了:

(defun double2 (L)
   (cond
      ((atom L) nil)
      (t (setf
             (cdr L)
             (cons (car L ) (double2 (cdr L))))
         L) ) )


(double2 (list 'a 'b 'c)) => (a a b b c c) 

Answer 1

这是另一种不使用递归的方法。请注意，此答案假设您正在做功课并试图找到一种方法来避免创建新列表，这是最简单的解决方案所做的。实际上，您只需在 loop 中使用 collect 两次，就像 Sylwester 演示的那样。这里原始输入列表被破坏性地修改。

复制列表

假设您的原始 list 是 (1 2 3)。而不是欺骗元素，你可以调用 (copy-list list)，它执行所需的数量。这就是你需要考虑的所有内存分配。然后，你“只”需要交错所有的缺点细胞获得所需的重复。

保持给定的list变量，并定义两个变量遍历两个列表:

current = (1 2 3) ;; original
  fresh = (1 2 3) ;; copy

重新排序单元格

从图形上看，您希望更改 CDR 以将现有的 cons-cell“串联”在一起。一开始，两个列表都是这样的:

  current   ( 1 . x-)-->( 2 . x-)-->...

  fresh     ( 1 . x-)-->( 2 . x-)-->...

但是你想要:

  current   ( 1 . x )   ( 2 . x )
                  |     ^     |
                  V     |     V
  fresh           ( 1 . x )   ( 2 . ...)

更正式地说，在每一步的开始，当你的列表不为空时，上面的变量可以分解如下:

current = (chead . ctail)
  fresh = (fhead . ftail)

你想让 current 的尾部指向 fresh cons-cell，并让 fresh 的尾部指向 尾部。完成交错单元格后，变量应按如下方式绑定(bind):

current = (chead . (fhead . ctail))
  fresh = ftail

然后，您可以在 current 中下降两次，因此最终:

current = ctail
  fresh = ftail

从这里，您可以继续两个列表的其余部分。注意list 仍然包含您作为输入。

代码

(defun double-loop (list)
  (loop
    with fresh = (copy-list list)                 ;; cursor to new cons cells
    with current = list                           ;; cursor to current cell
    while fresh                                   ;; stop when fresh is nil
    do (print (list list current fresh))          ;; for debugging
       (rotatef (cdr fresh) (cdr current) fresh)  ;; change CDRs, rebind fresh
       (setf current (cddr current))              ;; update CURRENT
    finally (return list)))                       ;; LIST points to head of result

我正在使用 ROTATEF连线缺点细胞:

(rotatef (cdr fresh) (cdr current) fresh)

fresh 的值被放置在 (cdr current) 中，其先前的值本身被放置在 (cdr fresh) 中>, 原来的其值最终成为绑定(bind)到 fresh 的新值。

例子

这是一个示例跟踪输出:

CL-USER> (double-loop (list 0 1 2 3))

((0 1 2 3) (0 1 2 3) (0 1 2 3)) 
((0 0 1 2 3) (1 2 3) (1 2 3)) 
((0 0 1 1 2 3) (2 3) (2 3)) 
((0 0 1 1 2 2 3) (3) (3))

=> (0 0 1 1 2 2 3 3)