Now, we look at sublis, and its relative nsublis.  You’ve probably realized by now that those functions with the ‘n’ prefix are generally destructive versions of the corresponding unprefixed function.  That is, the nsublis function is permitted to destroy its input tree.

What the sublis function does is to walk a tree and look up all subtrees and nodes as keys in the association list.  When a match is found, the value corresponding to that key is substituted.  A new tree is created that contains the substituted elements, and that may share elements with the input tree.  I will provide some examples below.

Note that the spec does not appear to provide any hard rules about the order of tree traversal, so the programmer should be careful to avoid changes that might feed back into themselves, as can happen with more complex :test functions.

Here are some examples of sublis use.  Note that if you provide your own test function it has to be able to handle receiving both sublists and nodes in its arguments.

CL-USER> (let ((swaps '((1 . "ONE")
                        (2 . "TWO")
                        (3 . "THREE")
                        (4 . "FOUR")))
               (demo-tree '((1 2)
                            (3 4 5 6)
                            (7 (8 9 10) 1))))
           (sublis swaps demo-tree))
(("ONE" "TWO") ("THREE" "FOUR" 5 6) (7 (8 9 10) "ONE"))
CL-USER> (labels
             ((same-type (x y)
                (and (numberp x)
                     (numberp y)
                     (= (mod x 2)
                        (mod y 2)))))
           (let ((types '((1 . "ODD")
                          (2 . "EVEN")))
                 (demo-tree '((1 2)
                              (3 4 5 6)
                              (7 (8 9 10) 1))))
             (pprint-linear t
                            (sublis types demo-tree 
                                    :test #'same-type))))

(("ODD" "EVEN")
 ("ODD" "EVEN" "ODD" "EVEN")
 ("ODD" ("EVEN" "ODD" "EVEN") "ODD"))
NIL