ADPfusion: Efficient, high-level dynamic programming.
ADPfusion combines stream-fusion (using the stream interface provided by the vector library) and type-level programming to provide highly efficient dynamic programming combinators.
This library is described in:
Christian Hoener zu Siederdissen Sneaking Around ConcatMap: Efficient Combinators for Dynamic Programming 2012. Proceedings of the 17th ACM SIGPLAN international conference on Functional programming http://doi.acm.org/10.1145/2364527.2364559 preprint: http://www.tbi.univie.ac.at/newpapers/pdfs/TBI-p-2012-2.pdf
From the programmers' viewpoint, ADPfusion behaves very much like the original ADP implementation http://bibiserv.techfak.uni-bielefeld.de/adp/ developed by Robert Giegerich and colleagues, though both combinator semantics and backtracking are different.
The library internals, however, are designed not only to speed up ADP by a large margin (which this library does), but also to provide further runtime improvements by allowing the programmer to switch over to other kinds of data structures with better time and space behaviour. Most importantly, dynamic programming tables can be strict, removing indirections present in lazy, boxed tables.
As a simple benchmark, consider the Nussinov78 algorithm which
translates to three nested for loops (for C). In the figure,
four different approaches are compared using inputs with size
100 characters to 1000 characters in increments of 100
characters. C is an implementation (.C directory) in C
using "gcc -O3". ADP is the original ADP approach (see link
above), while GAPC uses the GAP language
(http://gapc.eu/).
Performance comparison figure: http://www.tbi.univie.ac.at/~choener/adpfusion/gaplike-nussinov-runtime.jpg
Please note that actual performance will depend much on table layout and data structures accessed during calculations, but in general performance is very good: close to C and better than other high-level approaches (that I know of).
Even complex ADP code tends to be completely optimized to loops that use only unboxed variables (Int# and others, indexIntArray# and others).
Completely novel (compared to ADP), is the idea of allowing efficient monadic combinators. This facilitates writing code that performs backtracking, or samples structures stochastically, among others things.
Two algorithms from the realm of computational biology are provided as examples on how to write dynamic programming algorithms using this library: http://hackage.haskell.org/package/Nussinov78 and http://hackage.haskell.org/package/RNAFold.
[Skip to Readme]
Downloads
- ADPfusion-0.2.1.0.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
For package maintainers and hackage trustees
Candidates
- No Candidates
| Versions [RSS] | 0.0.1.0, 0.0.1.1, 0.0.1.2, 0.1.0.0, 0.2.0.0, 0.2.0.1, 0.2.0.2, 0.2.0.3, 0.2.0.4, 0.2.1.0, 0.4.0.0, 0.4.0.1, 0.4.0.2, 0.4.1.0, 0.4.1.1, 0.5.0.0, 0.5.1.0, 0.5.2.0, 0.5.2.2, 0.6.0.0 (info) |
|---|---|
| Change log | changelog |
| Dependencies | base (>=4 && <5), deepseq (>=1.3), ghc-prim, primitive (>=0.5), PrimitiveArray (>=0.5.3), QuickCheck (>=2.5), repa (>=3.2), strict (>=0.3.2), template-haskell, transformers, vector (>=0.10) [details] |
| License | BSD-3-Clause |
| Copyright | Christian Hoener zu Siederdissen, 2011-2013 |
| Author | Christian Hoener zu Siederdissen, 2011-2013 |
| Maintainer | choener@tbi.univie.ac.at |
| Category | Algorithms, Data Structures, Bioinformatics |
| Home page | http://www.tbi.univie.ac.at/~choener/adpfusion |
| Source repo | head: git clone git://github.com/choener/ADPfusion |
| Uploaded | by ChristianHoener at 2014-02-03T21:22:56Z |
| Distributions | |
| Reverse Dependencies | 15 direct, 1 indirect [details] |
| Executables | NeedlemanWunsch |
| Downloads | 19909 total (45 in the last 30 days) |
| Rating | (no votes yet) [estimated by Bayesian average] |
| Your Rating | |
| Status | Docs available [build log] Successful builds reported [all 1 reports] |