CODEWITHSUNDEEP
treecommon-lisp
davypough
davypough

Reputation: 1941

Finding an item in a tree in common lisp

I'm trying to write a function that can find an item in a tree, similar to the built-in find function for sequences. The call could look like (find-in-tree item tree :test test-fn :key key-fn). The hyperspec says the item passed to find can be any lisp object (that is, "any Lisp datum"), but the tree I have in mind is not the usual Lisp binary cons tree. The tree, call it a multitree, would be a (possibly recursive or dotted) list of atoms or lists. An example is (find-in-tree '(1 2) '(1 (2) nil (3 (1 2)) . 4) :test #'equal) => (1 2) or some non-nil value.

In looking around I came across some interesting code at http://lisptips.com/post/43404489000/the-tree-walkers-of-cl which, with suitable adaptations, does seem to work for the standard cons tree:

(defun find-in-tree (item tree &key (test #'eql))
  (catch 'find-in-tree
         (subst-if t (constantly nil) tree 
                   :key (lambda (element)
                          (when (funcall test element item)
                            (throw 'find-in-tree element))))
         nil))

However, I'm not sure how to adapt this (or build a recursive function) for a multitree.

Upvotes: 0

Views: 1148

Answers (1)

Rainer Joswig
Rainer Joswig

Reputation: 139251

Something like this. Use a local function for the recursion. From there one can escape from the recursion using return-from once the item is found.

CL-USER> (defun find-in-tree (item tree &key (test #'eql))                             
           (labels ((find-in-tree-aux (tree)                                           
                      (cond ((funcall test item tree)                                  
                             (return-from find-in-tree tree))                          
                            ((consp tree)                                              
                             (find-in-tree-aux (car tree))                             
                             (find-in-tree-aux (cdr tree))))))                         
             (find-in-tree-aux tree)))
FIND-IN-TREE                                                                           
CL-USER> (find-in-tree 3 '((2 (4 3)) 5))
3                                                                                      
CL-USER> (find-in-tree 12 '((2 (4 3)) 5))
NIL                                                                                    
CL-USER> (find-in-tree "foo" '(("bar" ("baz")) "foo") :test #'equalp)
"foo"                                                                   
CL-USER> (find-in-tree 6 '((2 (4 3 . 6)) 5))
6

and

CL-USER 14 > (defun find-in-tree (item tree &key (test #'eql) (key #'identity))
              (labels ((find-in-tree-aux (tree)                                   
                         (cond ((funcall test item (funcall key tree))
                                (return-from find-in-tree tree))
                               ((consp tree)
                                (find-in-tree-aux (car tree))
                                (find-in-tree-aux (cdr tree))))))
                (find-in-tree-aux tree)))
FIND-IN-TREE

CL-USER 15 > (find-in-tree "foo" '(("a" 10)
                                   (("b" 20)
                                    ("foo" 300))
                                   ("c" 40))
                           :test #'equalp
                           :key (lambda (i)
                                  (when (consp i)
                                    (first i))))
("foo" 300)

Node as a list of trees

CL-USER 1 > (defun find-in-tree (item tree &key (test #'eql) (key #'identity))
              (labels ((find-in-tree-aux (tree)                                   
                         (cond ((funcall test item (funcall key tree))
                                (return-from find-in-tree tree))
                               ((listp tree)
                                (mapc #'find-in-tree-aux tree)
                                nil))))
                (find-in-tree-aux tree)))
FIND-IN-TREE

Upvotes: 5

Related Questions