TBI-p-2012-2

Download: [Link to PDF]

Titel:
Sneaking Around concatMap: Efficient Combinators for Dynamic Programming

Author(s):
Christian Hoener zu Siederdissen

submitted to:
Proceedings of the 17th ACM SIGPLAN international conference on Functional programming

Abstract:
We present a framework of dynamic programming combinators that provides a high-level environment to describe the recursions typical of dynamic programming over sequence data in a style very similar to Algebraic Dynamic Programming (ADP). Using a combination of type-level programming and stream fusion leads to a substantial increase in performance, without sacrificing much of the convenience and theoretical underpinnings of ADP. We draw examples from the field of computational biology, more specifically RNA secondary structure prediction, to demonstrate how to use these combinators and what differences exist between this library, ADP, and other approaches. The final version of the combinator library allows writing algorithms with performance close to hand-optimized C code.

Link to publication:

Return to Index Return to List
Last modified: 2008-10-22 12:23:11 fall