list as function argument in Lisp

Question

i have the following code:

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

which accepts a number N and a list TREE and checks to see if N exists in the list TREE. pretty simple, but for some reason i keep getting this error when i call my function

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

is there an issue with the code? i'm very new to Lisp so maybe i'm just not seeing something very obvious.. thanks in advance!

Answer 1

Syntax errors

Your code contains several syntax errors that are flagged as compiler warnings:

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

The reason is that parentheses in Common Lisp have a meaning different from that of other programming languages: they are not used to specify the order of application of the operators (like in 3 * (2 + 4) which is different from 3 * 2 + 4), but are integral part of the syntax to specify the different parts of a “statement”, like in cond or in function application (like (function-name arg1 arg2 ... argn)). So the syntax error in this case is in the last line, in which you should call the function TREE-CONTAINS with arguments N and (cdr TREE) as:

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

Semantic errors

If you try this function, however, you will find an error:

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

 The value NIL is not of the expected type NUMBER.

The reason is that you have used = to compare a number ((car TREE)) with the value nil, while = can be used only to compare numbers. Use eq or eql instead for the general case:

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

There is also another problem: you should check if the list is empty, not if the first element is nil. In other words, the first condition should be:

(cond ((eq TREE nil) nil)

or better:

(cond ((null TREE) nil)

Stylistic notes

1. A list is a particular case of tree: if you use the term tree the program should be more complex, taking into account cases in which the elements can be sublists.

2. Use lowercase identifier, since everything is translated to upper-case

3. Put the close parentheses at the end of the expression, not on a new line.

So your function could be something like:

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

Check membership for a tree and not a list

If, on the other hand, you want to check for a generic tree, i.e. a list which can contain sublists, like in (tree-contains 3 '((1 2 3) 7 8)), in your recursion you should consider tha case in which an element of the list is itself a list, and then perform a double recursion. Here is a possible solution:

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

In addition to the accepted answer, here is an alternative way of writing the same predicate, without cond:

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