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

这项作业的问题是我无法与老师见面提问，因为他走了，而且现在“电子邮件访问权限有限”。我不能问如何解决这个问题，我什至不知道从哪里开始这个功能。我想我必须像 L1 的汽车一样使用 myMember 并检查它是否在 L2 中，如果它被放在一个新列表中并递归地添加到列表中。我不知道该怎么做。谁能帮我解决这个学期的问题？谢谢!

Answer 1

你的想法很好。您应该查看您在 myCount 中使用的模式。您可以对 myCommon 使用几乎相同的模式。

思考如何从递归中走出来。您正在构建一个列表，而不是一个数字，因此不要将 0 作为最终值，而是考虑列表的末尾是什么。

对于递归子句，当您应该包含项目时不要使用 +1，而是使用将项目添加到列表的函数。

记住只递归 myCommon 中的一个列表。您应该一次查看一个元素，并将该元素与完整的第二个列表进行比较，对于 myCommon 而言，第二个列表应该是一个常量。

希望这能本着您之前职能的精神对您有所帮助。但这是实现交集函数的一种非常低效的方法。

可以帮助您的编译器生成更高效代码的一个常见技巧是使用带有第三个参数的辅助函数 - 一个累加器，您在递归输入列表之一时构建该累加器。 (累加器技巧让您可以以称为尾递归的样式编写函数。)

当你不做人为限制的练习来学习递归时，我更愿意使用迭代(loop 或 dolist)来解决这个问题，尤其是当你使用common lisp，即使对于尾递归调用，它也不强制编译器生成有效的代码。但话又说回来，如果您不使用受限版本的 common lisp，您可以只调用内置函数 intersection。 :-)