Next: , Previous: Common List Functions, Up: Sorting and Searching

7.2.2 Tree operations

(require 'tree) These are operations that treat lists a representations of trees.

— Function: subst new old tree
— Function: substq new old tree
— Function: substv new old tree
— Function: subst new old tree equ?

subst makes a copy of tree, substituting new for every subtree or leaf of tree which is equal? to old and returns a modified tree. The original tree is unchanged, but may share parts with the result.

substq and substv are similar, but test against old using eq? and eqv? respectively. If subst is called with a fourth argument, equ? is the equality predicate.


          (substq 'tempest 'hurricane '(shakespeare wrote (the hurricane)))
             ⇒ (shakespeare wrote (the tempest))
          (substq 'foo '() '(shakespeare wrote (twelfth night)))
             ⇒ (shakespeare wrote (twelfth night . foo) . foo)
          (subst '(a . cons) '(old . pair)
                 '((old . spice) ((old . shoes) old . pair) (old . pair)))
             ⇒ ((old . spice) ((old . shoes) a . cons) (a . cons))
— Function: copy-tree tree

Makes a copy of the nested list structure tree using new pairs and returns it. All levels are copied, so that none of the pairs in the tree are eq? to the original ones – only the leaves are.


          (define bar '(bar))
          (copy-tree (list bar 'foo))
             ⇒ ((bar) foo)
          (eq? bar (car (copy-tree (list bar 'foo))))
             ⇒ #f