LISP Function that Returns True If Atom Is In List

Question

I'm trying to write a function (deep-find) that takes in a list and another argument and returns T if that argument is present in the list. For example, if I called (deep-find '(A B (C D)) 'C) it should return true, but if I called (deep-find '(A B (C D)) 'F) it should return false. Here's the code I have so far, but it returns nil every time:

(defun deep-find (L n)
  (cond
   ((null L) nil)
   ((equal n (car L)) t)
   ((deep-find (cdr L) n))))

Answer 1

Your code does not return NIL every time; it works well for simple lists. For instance (deep-find '(A B (C D)) 'A) returns T as it should.

You have three cases in your cond: end of list, list head check, and list tail check. However, there is nothing regarding trees in that. So, you need another condition that recurses into the deeper levels of a tree in case of a branch in the tree:

(defun deep-find (L n)
  (cond
   ((null L) nil)
   ((equal n (car L)) t)
   ((listp (car L))             ; in case of a branch,
    (or (deep-find (car L) n)   ; check the branch,
        (deep-find (cdr L) n))) ; and check rest of the list
   ((deep-find (cdr L) n))))

Answer 2

Sometimes this kind of problem becomes easier if you add more flexibility.

For example considering generic binary trees instead of just lists (that are a specific sub-case of binary trees) and also assuming that the correct answer for (deep-find 'a 'a) should be T the code becomes shorter and more elegant:

(defun deep-find (tree item)
  (or (equal tree item)
      (and (consp tree)
           (or (deep-find (car tree) item)
               (deep-find (cdr tree) item)))))