Lisp-check for a node in a n-tree

Question

I have a n-tree represented as a nonlinear list. The tree is represented as (root list_of_nodes_subtree1 ... list_of_nodes_subtreen). I need to write a function that tests whether a specific node belongs to the n-tree and i HAVE to use a map function. I guess the right one is mapcar, but i'm not too sure. I've tried several times, but I'm not familiar with lambda functions and i'm not sure if i need to use them or not.

Example: for a tree represented as (a (b (c)) (d) (e (f))) and node e => true

Answer 1

If just t or nil as a result suffices, you could also do:

(defun node-in-tree (node tree &key (test #'eql))
  (eq t (mapcar (lambda (x) (if (listp x) 
                                (when (node-in-tree node x) (return-from node-in-tree t))
                                (when (funcall test node x) (return-from node-in-tree t))))
                tree)))

The trick here is that return-from can manage to break-out from a lambda in a mapcar as soon as one occasion positive for (funcall test node x) occurs. Therefore it is secured that this function stops its investigation as soon as the node is found. (eq t ...) is necessary because the list that mapcar returns as long as not '() would be interpreted as true although it might consist of only nils as elements.

Okay, I see, one can get rid of the (eq t ...) when using (map nil ...) instead of (mapcar ...) like @ignisvolens did:

(defun node-in-tree (node tree &key (test #'eql))
  (map nil (lambda (x) (if (listp x) 
                           (when (node-in-tree node x) (return-from node-in-tree t))
                           (when (funcall test node x) (return-from node-in-tree t))))
       tree)))

Slightly more elegant is mapcan which give for (nil nil nil ...) as a result of mapcar or (map nil ...) simply a '().

(defun node-in-tree (node tree &key (test #'eql))
  (mapcan (lambda (x) (if (listp x) 
                          (when (node-in-tree node x) (return-from node-in-tree t))
                          (when (funcall test node x) (return-from node-in-tree t))))
          tree))))

The lambda function can be summarized to:

Final solution

(defun node-in-tree (node tree &key (test #'eql))
  (mapcan (lambda (x) (when (or (and (listp x) (node-in-tree node x)) 
                                (funcall test node x)) 
                        (return-from node-in-tree t)))
          tree))

Or also good:

(defun node-in-tree (node tree)
  (if (atom tree) 
      (eql node tree)
      (mapcan #'(lambda (x) (if (node-in-tree node x) (return-from node-in-tree t))) 
              tree)))