Patrick Bahr IT University of Copenhagen

Programming Macro Tree Transducers

Patrick Bahr, presenting joint work with Laurence E. Day
Talk, Functional Programming Lab Away Day, Cressbrook Hall, Buxton, England, 13/06/2013.


Tree transducers are tree automata defining functions from trees to trees. Put simply, a tree transducer is a set of mutually recursive functions transforming an input tree into an output tree. Macro tree transducers extend this recursion scheme by allowing each function to be defined in terms of an arbitrary number of accumulation parameters. We show how macro tree transducers can be concisely represented in Haskell, and demonstrate the benefits of utilising such an approach with a number of examples. In particular, tree transducers afford a modular programming style as they can be easily composed and manipulated. Our Haskell representation generalises the original definition of (macro) tree transducers, abolishing a restriction on finite state spaces. However, as we demonstrate, this generalisation does not affect compositionality.

Categories: Recursion Schemes, Type Systems, Functional Programming

Tags: Tree Automaton, Transducer, Accumulation, Composition, Deforestation, Haskell, Recursion Scheme, Nested Recursion, Polymorphism