是否可以限制在duplicate（）函数中调用cons函数的次数？

问题描述：

我写了复制在列表中的项目如下功能double()：是否可以限制在duplicate（）函数中调用cons函数的次数？

(defun duplicate (l) 
    (if (null l) nil 
     (cons (car l) (cons (car l) (duplicate (cdr l))))))

的duplicate()功能做出两次调用CONS功能为每个项目在列表中：

Break 1 [2]> (trace cons) 
;; Traçage de la fonction CONS. 
(CONS) 

Break 1 [2]> (duplicate '(1 2 3)) 
1. Trace: (CONS '3 'NIL) 
1. Trace: CONS ==> (3) 
1. Trace: (CONS '3 '(3)) 
1. Trace: CONS ==> (3 3) 
1. Trace: (CONS '2 '(3 3)) 
1. Trace: CONS ==> (2 3 3) 
1. Trace: (CONS '2 '(2 3 3)) 
1. Trace: CONS ==> (2 2 3 3) 
1. Trace: (CONS '1 '(2 2 3 3)) 
1. Trace: CONS ==> (1 2 2 3 3) 
1. Trace: (CONS '1 '(1 2 2 3 3)) 
1. Trace: CONS ==> (1 1 2 2 3 3) 
(1 1 2 2 3 3)

是它可能将每个列表项目的呼叫次数限制为CONS？

归根结底，没有，因为'cons'只增加一个项目名单，并且在每一步添加两个项目。 – chepner

我们不能将'cons'函数与lisp映射函数结合起来解决这个问题吗？ – lukas

我认为这取决于你的实现是否有任何优化连接两个列表。在概念上（我认为），任何构建新列表的任何事都可以通过将一个元素一次添加到任意长列表的前面来完成。 – chepner

答

不，由于相同的原因，您不能使用5升水填充10升桶。

10个元素的列表需要10个cons单元。

谢谢你的帮助。您的评论确认我的意见 – lukas

答

破坏性的版本将使其成为可能：

(defun duplicate (l) 
    (if (null l) 
     nil 
    (destructuring-bind (f . r) 
     l 
     (setf (cdr l) 
      (cons f (duplicate r))) 
     l))) 

CL-USER 10 > (duplicate (list 1 2 3 4 5)) 
(1 1 2 2 3 3 4 4 5 5)

答

可以消除所有的利弊呼吁：

(list* (car l) (car l) (duplicate (cdr l)))

您如何确定在任何Common Lisp实现中'list *'不会调用'cons'？ – Sylwester

在某种程度上，我一直很face，，但我也认为OP可能更希望能够避免*编码*两个cons调用，因此提供了更好的'list *'语法。但回过头来看，我发现“痕迹”被视为真相的源泉，所以我的水晶球可能会让我失望。 – kennytilton

是否可以限制在duplicate（）函数中调用cons函数的次数？

相关推荐