ComputingComputer EngineeringComputer ScienceAlgebraCompilersProgramming LanguagesCompiler ConstructionCompositional SemanticsData TypesGeneric ProgrammingRecursion TheoryType SystemsAlgebraic Data TypesCompiler DesignCompiler SupportMonadic SemanticsRecursionRecursion SchemesRecursive TypesReuse
Building on Wouter Swierstra's Data types à la carte, we present a comprehensive Haskell library of compositional data types suitable for practical applications. In this framework, data types and functions on them can be defined in a modular fashion. We extend the existing work by implementing a wide array of recursion schemes including monadic computations. Above all, we generalise recursive data types to contexts, which allow us to characterise a special yet frequent kind of catamorphisms. The thus established notion of term homomorphisms allows for flexible reuse and enables short-cut fusion style deforestation which yields considerable speedups. We demonstrate our framework in the setting of compiler construction, and moreover, we compare compositional data types with generic programming techniques and show that both are comparable in run-time performance and expressivity while our approach allows for stricter types. We substantiate this conclusion by lifting compositional data types to recursive data types and generalised algebraic data types. Lastly, we compare the run-time performance of our techniques with traditional implementations over algebraic data types. The results are surprisingly good.
17
Tree automata techniques and applications
Hubert Comon, Max Dauchet, Florent Jacquemard et al. · 1997 · 1.2K citations · Full text
Template meta-programming for Haskell
Tim Sheard, Simon Peyton Jones · 2002 · 548 citations
Andrew Gill, John Launchbury, Simon Jones · 1993 · 415 citations · Full text
Applicative programming with effects
Conor McBride, Ross Paterson · Journal of Functional Programming · 2007 · 402 citations · Full text
Wouter Swierstra · Journal of Functional Programming · 2008 · 282 citations · Full text