You can find a matching subtree in time independent of the number of patterns using essentially the same idea as the Aho-Corasick method of string pattern match

You can find a matching subtree in time independent of the number of patterns using essentially the same idea as the Aho-Corasick method of string pattern matching. This is done in term rewriting systems -- e.g. I just looked up the Pure term-rewriting language and this code appears to work that way (just going by the comment): https://bitbucket.org/purelang/pure-lang/src/b7486ed110e5c509cd329b335a83ff74ca77d750/pure/matcher.hh?at=default&fileviewer=file-view-default#matcher.hh-147 https://bitbucket.org/purelang/pure-lang/src/b7486ed110e5c50... You could try out your idea by expressing your optimizer rules as a program in Pure. I don't know if after a rewrite they rescan the tree from the root, or try to get smarter and restart the matcher automaton from a point only just far enough up the tree (and back in the matcher) to allow for any change from the rewrite. It might be interesting to apply Rete directly to the tree represented as a set of tuples, for instance (define (double x) (* 2 x)) as (root G0) (branch G0 define G1 G2) (branch G1 double x) (branch G2 * 2 x) and now a rewrite like (* 2 N) => (+ N N) would go (rule (branch ?name * 2 ?node) => (branch ?name + ?node ?node)) I'd be surprised if this worked out better in general, but maybe there are some interesting cases. BTW the GHC compiler for Haskell lets library authors define optimizations by rewrite rules -- like your array of records to record of arrays, I guess.