The tree-walkers of CL

Дата публікації:
18/02/2013 18:11

Постійна адреса новини:
http://www.vsinovyny.com/8323835

The tree-walkers of CL

18/02/2013 18:11 // Common Lisp Tips

If you need to visit a tree in some way, there are two built-in functions that, while not explicitly designed for the purpose, can walk a tree effectively.

First, subst-if takes a predicate function that is called for each cons and atom in a tree. As long as the predicate returns nil, no substitution will actually take place.

Here’s a simple way to turn it into a function:

(defun walk-tree (fun tree)
  (subst-if t
            (constantly nil)
            tree
            :key fun))

* (walk-tree 'print '(a b (1 2 . 10) c))

(A B (1 2 . 10) C) 
A 
(B (1 2 . 10) C) 
B 
((1 2 . 10) C) 
(1 2 . 10) 
1 
(2 . 10) 
2 
10 
(C) 
C 
NIL 
(A B (1 2 . 10) C)

Second, tree-equal is normally considered for comparing two trees, but it can also be used to call a function for each atom in a single tree; just pass the same tree to tree-equal, and use the test function to do something with each atom. As long as the test function returns true, the walking continues.

Here’s a function that wraps it up:

(defun walk-tree-atoms (fun tree)
  (tree-equal tree tree
              :test (lambda (element-1 element-2)
                      (declare (ignore element-2))
                      (funcall fun element-1)
                      t)))

* (walk-tree-atoms 'print '(a b (1 2 . 10) c))

A 
B 
1 
2 
10 
C 
NIL 
T

(This tip inspired by a few articles from Rob Warnock.)

» Читати повністю

«	Наступна новина з архіву Semicolon style	Попередня новина з архіву Duplicated keyword arguments	»