如何在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))))