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.
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.
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.
This version is still highly experimental and makes use of multiple recent improvements in GHC. This is particularly true for the monadic interface.
Long term goals: Outer indices with more than two dimensions, specialized table design, a combinator library, a library for computational biology.
If possible, build using the GHC llvm backend, and GHC-7.2.2. GHC-7.4.x produces very bad code on my system, please benchmark using 7.2.2.
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]
|Versions||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 (info)|
|Dependencies||base (==4.*), primitive (==0.4.*), PrimitiveArray (==0.2.1.1), vector (==0.9.*) [details]|
|Copyright||Christian Hoener zu Siederdissen, 2011-2012|
|Author||Christian Hoener zu Siederdissen, 2011-2012|
|Category||Algorithms, Data Structures, Bioinformatics|
|Source repo||head: git clone git://github.com/choener/ADPfusion|
|Uploaded||by ChristianHoener at Sun Mar 25 01:35:30 UTC 2012|
|Downloads||8151 total (49 in the last 30 days)|
|Rating||(no votes yet) [estimated by rule of succession]|
|Status||Docs uploaded by user
Build status unknown [no reports yet]
Hackage Matrix CI
build using llvm backend
Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info
For package maintainers and hackage trustees