列表作为Lisp中的函数参数

Question

我有以下代码:

(defun TREE-CONTAINS (N TREE)
  (cond (( = (car TREE) nil) nil)
        (( = (car TREE) N) t)
         (t TREE-CONTAINS (N (cdr TREE)))
  )
)

它接受一个数字N和一个列表TREE,并检查列表TREE中是否存在N. 非常简单,但由于某种原因,当我调用我的函数时,我不断收到此错误

(TREE-CONTAINS 3 '((1 2 3) 7 8))
*** - +: (1 2 3) is not a number

代码有问题吗？我是Lisp的新手,所以也许我只是没有看到一些非常明显的东西..提前感谢!

Answer 1

语法错误

您的代码包含多个语法错误,这些错误被标记为编译器警告:

CL-USER> (defun TREE-CONTAINS (N TREE)
           (cond (( = (car TREE) nil) nil)
                 (( = (car TREE) N) t)
                 (t TREE-CONTAINS (N (cdr TREE)))
            )
          )
;Compiler warnings :
;   In TREE-CONTAINS: Undeclared free variable TREE-CONTAINS
;   In TREE-CONTAINS: Undefined function N
TREE-CONTAINS

原因是Common Lisp中的括号具有与其他编程语言不同的含义:它们不用于指定运算符的应用顺序(如3 * (2 + 4)与其不同3 * 2 + 4),但它们是指定语法的组成部分"声明"的不同部分,如cond在函数应用程序中或在函数应用程序中(如(function-name arg1 arg2 ... argn)).因此,本例中的语法错误位于最后一行,您应该TREE-CONTAINS使用参数调用该函数N,(cdr TREE)如下所示:

CL-USER> (defun TREE-CONTAINS (N TREE)
           (cond (( = (car TREE) nil) nil)
                 (( = (car TREE) N) t)
                 (t (TREE-CONTAINS N (cdr TREE)))
            )
          )
TREE-CONTAINS

语义错误

但是,如果您尝试此功能,则会发现错误:

 CL-USER> (TREE-CONTAINS 2 '(1 2 3))

 The value NIL is not of the expected type NUMBER.

原因是您已经习惯=将数字((car TREE))与值进行比较nil,而=只能用于比较数字.使用eq或eql代替一般情况:

CL-USER> (defun TREE-CONTAINS (N TREE)
           (cond (( eql (car TREE) nil) nil)
                 (( = (car TREE) N) t)
                 (t (TREE-CONTAINS N (cdr TREE)))
            )
          )
TREE-CONTAINS

CL-USER> (TREE-CONTAINS 2 '(1 2 3))
T

还有另一个问题:你应该检查列表是否为空,而不是第一个元素是否为零.换句话说,第一个条件应该是:

(cond ((eq TREE nil) nil)

或更好:

(cond ((null TREE) nil)

文体笔记

1. 列表是树的特例:如果使用术语树,则程序应该更复杂,考虑到元素可以是子列表的情况.

2. 使用小写标识符,因为所有内容都转换为大写

3. 将紧密括号放在表达式的末尾,而不是新行.

所以你的功能可能是这样的:

(defun list-contains (n list)
  (cond ((null list) nil)
        ((= (car list) n) t)
        (t (list-contains n (cdr list)))))

检查树的成员资格而不是列表

另一方面,如果要检查通用树,即可以包含子列表的列表,例如(tree-contains 3 '((1 2 3) 7 8)),在递归中,您应该考虑列表中的元素本身就是列表的情况,然后执行双递归.这是一个可能的解决方案:

CL-USER> (list-contains 2 '(1 (2 3) 4))

The value (2 3) is not of the expected type NUMBER.

CL-USER> (defun tree-contains (n tree)
           (cond ((null tree) nil)
                 ((listp (car tree)) (or (tree-contains n (car tree))
                                         (tree-contains n (cdr tree))))
                 ((= (car tree) n) t)
                 (t (tree-contains n (cdr tree)))))
 TREE-CONTAINS
 CL-USER> (tree-contains 2 '(1 (2 3) 4))
 T

Answer 2

除了接受的答案之外,这里还有另一种编写相同谓词的方法,不需要cond:

(defun list-contains-p (number list)
  (and (consp list)
       (or (= number (first list))
           (list-contains-p number (rest list)))))