如何在LISP中插入2个列表的元素？

Question

给定2个列表，你怎样才能生成第三个列表的输出，它的元素是L1和L2的交错集合？如果它们长度不均匀，则应该插入零孔。在第二个音符上，我该如何反转一个列表？我对LISP超级新手，只是修改现有的代码...我真的很喜欢有一个很好的解释，而不仅仅是代码。

Answer 1

首先，我猜你使用Common Lisp，因为它是Lisp课程中最常用的一个。所以，我的例子将在CL。如果你使用Scheme，你将得到几乎相同的代码。如果现代Clojure，它将需要一些改变，通过一个想法将是相同的。

交错

交错2只列出了必须要经过他们两个，收集轮流元素。你可以使用循环语句或递归来做到这一点。我将使用递归，因为它具有更多的功能风格，并且可以在任何lisp中使用，而不仅仅是CL。还要注意，有一个名为tail recursion的功能，它可以让您编写将被编译为循环的递归函数。
因此，对于我们的函数骨架结构将是：

(defun interleave (l1 l2) 
    ?????? 
     (interleave ?????)) 

收集在递归函数的项目，你将需要从每个调用返回他们，然后负面因素在一起（你必须有一个参数一个尾递归，这将积累价值）。所以，该功能的结束将是(cons current-value (interleave ????))。 此外，您必须备用列表才能使用彼此的元素。您可能有其他参数，但您也可以在递归调用中交换它们。因此，代码变为：

(defun interleave (l1 l2) 
    ????? 
    (cons current-value (interleave l2 l1))) 

任何递归都必须在某处停止。在这种情况下，当两个列表都为空（零）时，它必须停止。 这是一个条件（让它给号码1），并且还有一些条件：
2.如果要从其中取出的列表是空的，而另一个不是，我们必须取而代之。
3.如果两个列表都不为空，则将第一个元素作为当前值并继续处理它的尾部。

只有一个更多的条件，2列表可以在：列表采取是不是空的，第二个是。但实际上我们并不关心这个，并且可以与规则编号前进3 因此，该代码（这是最后一个）：

(defun interleave (l1 l2) 
    (cond ((and (eql l1 nil) (eql l2 nil)) nil)   ;; rule #1 
     ((eql l1 nil) (cons nil (interleave l2 l1))) ;; rule #2, current value is nil 
     (true (cons (first l1) (interleave l2 (rest l1)))))) ;; rule #3 in all other cases 

反向

我我们将展示这个函数的两个实现：一个使用cond，另一个使用内置的reduce函数，这在实践中非常有用。

为cond版本第一种方法是要经过所有的列表与递归调用，然后回去，收集要素：

(defun reverse-1-1 (li) 
    (if (eql li nil) 
     nil 
     (append (reverse-1-1 (rest li)) 
       (list (first li))))) 

但是，这是非常低效的，因为append为O(n)，你必须通过n个元素，所以最终的复杂度是O（n^2）。

要减少它，你可以使用一个多参数的函数（并使其尾递归，如果编译器可以让你）：

(defun reverse-1-2 (li) 
    (reverse-aux li nil)) 

(defun reverse-aux (li accumulator) 
    (if (eql li nil) 
     accumulator 
     (reverse-aux (rest li) (cons (first li) accumulator)))) 

这就是你用一个参数来收集你的元素，但通过该列表，然后只是返回这个累加器。

还有一个更有趣的选项。 Lisp具有非常强大的功能reduce（在其他功能语言中，它有时被称为fold，foldr,foldl或类似的东西）。您可能会发现说明它here，我会只显示一个例子：

(defun reverse-2 (li) 
    (reduce #'cons li :from-end t :initial-value nil)) 

:from-end告诉函数要经过单从末尾，：初始值告诉作为首先减少使用论点nil。

注意：在某些实现中，减少选项:from-end true可能首先自行反向列表，因此如果您需要从头创建或使用最有效的版本，请改为使用reverse-1-2。

Answer 2

Common Lisp中：

(defun merge-lists (lst1 lst2) 
    (let ((m (max (length lst1) (length lst2)))) 
    (flatten (mapcar (lambda (a b) (list a b)) 
        (append-nulls lst1 m) 
        (append-nulls lst2 m))))) 

实例：

(merge-lists '(1 2 3 4) '(5 6 7 8)) ;; => (1 5 2 6 3 7 4 8) 
(merge-lists '(1 2 3 4) '(5 6 7)) ;; => (1 5 2 6 3 7 4 NULL) 
(merge-lists '(1 2) '(5 6 7 8)) ;; => (1 5 2 6 NULL 7 NULL 8) 

的辅助函数flatten和append-nulls：

答案上述

(defun flatten (tree) 
    (let ((result '())) 
    (labels ((scan (item) 
       (if (listp item) 
        (map nil #'scan item) 
        (push item result)))) 
     (scan tree)) 
    (nreverse result))) 

(defun append-nulls (lst n) 
    (if (< (length lst) n) 
     (dotimes (i (- n (length lst))) 
     (setq lst (append lst (list 'null))))) 
    lst) 

Answer 3

：

(defun interleave (l1 l2) 
    (cond ((and (eql l1 nil) (eql l2 nil)) nil)   ;; rule #1 
     ((eql l1 nil) (cons nil (interleave l2 l1))) ;; rule #2, current value is nil 
     (true (cons (first l1) (interleave l2 (rest l1)))))) ;; rule #3 in all other cases 

如果其中一个列表比另一个长，你会得到类似于（1 2 3 4 nil 5）的东西。 替换： （（EQL L1无）（利弊零（交织L2 L1）））

用： （（空L1）L2）

：P

Answer 4

的更惯用的一个例子在Common Lisp中的解决方案：

(defun interleave (a b) 
    (flet ((nil-pad (list on-list) 
      (append list (make-list (max 0 (- (length on-list) (length list))))))) 
    (loop for x in (nil-pad a b) 
      for y in (nil-pad b a) 
      append (list x y))))