Deriving Modular Recursion Schemes from Tree Automata
Talk, Computing Science Colloquium, Utrecht University, The Netherlands, 12/04/2012.
Abstract
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