Algebraic Dynamic Programming (ADP) as an eDSL in Haskell
This repository contains an implementation of Algebraic Dynamic Programming (ADP) as Domain Specific Language which is embedded into the (general purpose) language Haskell. The implementation is also called Haskell-ADP.
Haskell-ADP uses the technique of parser combinators.
examples contains several Haskell-ADP programs that use
different variants of parser combinators.
Most of the combinators and examples are published in:
- Robert Giegerich, Carsten Meyer, and Peter Steffen. A discipline of dynamic programming over sequence data. Science of Computer Programming, 51(3):215-263, June 2004.
Dynamic programming is a classical programming technique, applicable in a wide variety of domains such as stochastic systems analysis, operations research, combinatorics of discrete structures, flow problems, parsing of ambiguous languages, and biosequence analysis. Little methodology has hitherto been available to guide the design of such algorithms. The matrix recurrences that typically describe a dynamic programming algorithm are difficult to construct, error-prone to implement, and, in nontrivial applications, almost impossible to debug completely. This article introduces a discipline designed to alleviate this problem. We describe an algebraic style of dynamic programming over sequence data. We define its formal framework, based on a combination of grammars and algebras, and including a formalization of Bellman's Principle. We suggest a language used for algorithm design on a convenient level of abstraction. We outline three ways of implementing this language, including an embedding in a lazy functional language. The workings of the new method are illustrated by a series of examples drawn from diverse areas of computer science.
See also the example source code for additional references.
Bellman's GAP Café also contains a bibliography of ADP related publications.
ADPCombinators.lhs- Basic set of ADP combinators for single-track programs
ADPTriCombinators.lhs- Variation on the tabulation method
TTCombinators.lhs- Combinators for a restricted set of two-track programs (i.e. alignment style algorithms)
Parser.lhs- Two-track combinators as used by RNAhybrid
Single- or two-track refers to the number of input tracks - i.e. a single- or two-track program works one or two input sequences/strings.
ElMamun.lhs- Optimization of terms regarding the use of parentheses
MatrixMult.lhs- Optimal matrix chain multiplication
LocSim.lhs- Optimal local alignment (using a similarity score model) while using the trick
x$rev(y)to encode two-track input as single-track input
AffineLocSim.lhs- Optimal local alignment with affine gap costs
AffineGlobSim.lhs- Optimal global alignment with affine gap costs
- Nussinov.lhs - The Nussinov (1978) algorithm for secondary structure prediction
- ShapeCombinatorics.lhs - Shape analyses of RNA sequences (where shape are classes of RNA secondary structures)
- Zuker.lhs - RNA secondary structure folding algorithm by Zuker (1981)
- CanonicalRNA.lhs - Complete suboptimal folding of canonical RNA structures
- CanonicalRNAnoDangle.lhs - Complete suboptimal folding of canonical RNA structures (no dangling bases)
- NeedlemanWunsch.lhs - The Needleman-Wunsch Algorithm for computing the global sequence alignment
- Waterman.lhs - Quadratic runtime variant of the above algorithm with a simple cost function
- SmithWaterman.lhs - Local alignment variant (Smith-Waterman Algorithm)
- ShortInLong.lhs - Local alignment variant
- Gotoh.lhs - Variant with affine gap costs (Gotoh 1982)
- Canon.lhs - Canonical alignments
RNAhybrid.lhs- Prediction of microRNA/target duplexes as in RNAhybrid
$ ghci examples/ElMamun.lhs *ElMamun> bill seller "1+2*3*4+5"  *ElMamun> bill (seller***prettyprint) "1+2*3*4+5" [(81,"((1+2)*(3*(4+5)))"),(81,"(((1+2)*3)*(4+5))")] *ElMamun> bill (seller***count) "1+2*3*4+5" [(81,2)] $ ghc -iexamples examples/RNAhybrid.lhs $ ghci -iexamples examples/RNAhybrid.lhs Prelude RNAhybrid> hybridise (mfe***prettyprint) ("gcauggcugauauuaugcaacaauucuaccucagcccugagcugcg", "ugagguaguagguuguauagu") [(-18.1,(5,"G GA G AU U"," GCU UAUUAU CAACA UC "," UGA GUAGUA GUUGU AG "," G G AU U"))]
Especially for questions regarding this repository contact:
Georg Sauthoff <firstname.lastname@example.org>
You can also contact the authors of the referenced literature (see the first page of each paper for contact details).