LISP通用列表功能

Question

嘿傢伙我有最後一個問題我試圖解決我的學期。我需要創建：

(myCommon L1 L2) 
Evaluates to a list of elements that are common in both lists L1 and L2. 
Assume L1 and L2 have no repeated elements. 
eg. (myCommon ‘(p a e g) ‘(a q r e)) → (a e) 

我只能用以下功能：

(atom X)    
(quote X)   
‘X   
(eq X Y)    
(cons X L)   
(car L)   
(cdr L)   
(list A B C)   
(if X Y Z)  . 
(cond (C1 S1) (C2 S2) …… (Cn Sn))  
(lambda (P1 P2 …… Pn) E)   
(funcall F (P1 P2 …… Pn)) 

我還可以用我已分配中創建的功能。到目前爲止，我已經創建了：

(defun myLast (L) 
    (if (eq (cdr L) '()) 
    (car L) 
    (myLast (cdr L))))    ;Evaluates to the last element of list L 

(defun myCount (X L) 
    (cond ((eq L '()) 0) 
    ((eq X (car L))(+ 1 (myCount X (cdr L)))) 
    (+ (myCount X (cdr L))))) ;Evaluates to number of occurrences of X in L 

(defun myMember (X L) 
    (cond ((eq L '()) '()) 
    ((eq X (car L)) t) 
    (t (myMember X (cdr L))))) ;Evaluates to true if X in L, false otherwise 

這個分配的問題是我不能碰見老師問問題作爲了HES，並具有「有限的電子郵件訪問」現在。我不能問如何解決這個問題的問題，我甚至對從哪裏開始這個功能感到困惑。我想我必須像L1的車一樣使用myMember，並檢查它是否在L2中，是否將它放在新列表中並遞歸添加到列表中。我不知道如何做到這一點。任何人都可以幫助我，所以我最終可以完成這個學期？謝謝！

Answer 1

你的想法是一個很好的想法。你應該看看你在myCount中使用的模式。您可以對myCommon使用幾乎相同的模式。

想想如何從遞歸的底部出來。您正在建立一個列表，而不是一個數字，因此，不要將0作爲終端值，而要考慮列表的結尾是什麼。

對於遞歸子句，不要在應該包含該項目時使用+ 1，而要使用將項目添加到列表的函數。

記住只對myCommon中的某個列表進行遞歸。您應該一次查看一個元素，並將該元素與完整的第二個列表進行比較，該列表對於myCommon而言應該是常量。

希望這應該能夠幫助你，順應你以前的職能精神。但這是實現交叉函數的一種非常低效的方式。

可以幫助您的編譯器生成更高效的代碼的一個常用技巧是使用具有第三個參數的輔助函數 - 一個累加器，您可以在輸入一個輸入列表時生成累加器。 （累加器招讓你寫你的函數的風格稱爲尾recusive。）

而當你沒有進行人爲限制excercises學習遞歸，我更喜歡使用迭代（loop或dolist）來解決這個問題，特別是當你使用通用的lisp時，它並不要求編譯器生成高效的代碼，即使對於尾遞歸調用。但是，如果您不使用通用lisp的限制版本，則可以調用內置函數intersection。 :-)