CODEWITHSUNDEEP
treecommon-lisp
zzymry
zzymry

Reputation: 3

Lisp-check for a node in a n-tree

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

Upvotes: 0

Views: 314

Answers (3)

Gwang-Jin Kim
Gwang-Jin Kim

Reputation: 9865

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)))

Upvotes: 1

ignis volens
ignis volens

Reputation: 9252

So, first of all let's not program like it's 1956. Let's instead imagine that rather than every function knowing all about the gory details of the representation of the tree which makes them long, hard to read, and brittle, data abstraction has been invented, and there are two functions:

  • node-value returns the value of a node;
  • node-children returns the children of a node as a list.

So then our function is going to look like this:

Is the value we're looking for the node-value of the node? If it is we're done, if not not try each child of the node.

So the obvious way to write this would be

(defun value-in-tree-p (value node &optional (test #'eql))
  (or (funcall test (node-value node) value)
      (dolist (n (node-children node) nil)
        (when (value-in-tree-p value n test)
          (return-from value-in-tree-p t)))))

But we're required to use a mapping function so, well, we can do that:

(defun value-in-tree-p (value node &optional (test #'eql))
  (or (funcall test (node-value node) value)
      (map nil (lambda (n)
                 (when (value-in-tree-p value n test)
                   (return-from value-in-tree-p t)))
           (node-children node))))

That's only a little harder to read.

All that is left is to write node-value and node-children, and make-node to make trees.

Upvotes: 2

MattArmstrong
MattArmstrong

Reputation: 384

You probably want a function that takes two arguments: a tree and the symbol to look for. It could call mapcar, passing it the tree and a lambda. The lambda examines each element of the list and if it is a symbol it evaluates (eq needle element), otherwise the element must be a subtree and it recurses. On the result of this, it calls reduce to turn the list of boolean values to a single value. Something like:

;; Look for NEEDLE in TREE.  NEEDLE should be a symbol.  TREE should
;; be a list of symbols or subtrees.  Return t if NEEDLE is in TREE,
;; NIL otherwise.
(defun is-symbol-in-tree (needle tree)
  (reduce #'or
          (mapcar #'(lambda (element)
                      (cond
                        ((symbolp element) (eq element needle))
                        ((consp element)
                         (symbol-in-tree target-sym element))
                        (t (error "unexpected element in tree"))))
    :initial-value nil))

I didn't test that code, but that is the idea. :-)

References: http://clhs.lisp.se/Body/f_mapc_.htm and http://clhs.lisp.se/Body/f_reduce.htm

If this kind of programming confuses you I recommend reading "A Gentle Introduction to Common Lisp" by David Touretzky. It introduces the concepts very clearly, in a simple way, from first principles. It does not assume the reader understands programming at all, which I found helpful because when I learned Common Lisp I had 30 years of programming experience in C and C++ to "unlearn."

I find that this kind of "applicative" style of coding makes the code flow inside out. E.g. in the example above the reduce appears before the mapcar even though it will be evaluated last. I'm still just a beginner in Common Lisp, by the way.

Upvotes: 1

Related Questions