Deriving Modular Recursion Schemes from Tree Automata
In this talk I present various kinds of well-known tree automata and show how to implement these automata in Haskell. Subsequently, I refine the thus obtained recursion schemes in order to derive modular and extensible recursion schemes. Functions that are specified in terms of these recursion schemes can be combined, reused and transformed in many ways. This flexibility facilitates the specification of complex transformations in a concise manner, which I illustrate with a number of examples.
Categories: Recursion Schemes, Functional Programming
Tags: Tree Automaton, Transducer, Acceptor, Modularity, Attribute Grammar, Recursion, Compiler, Haskell