name: ADPfusion
version: 0.2.0.3
author: Christian Hoener zu Siederdissen, 2011-2013
copyright: Christian Hoener zu Siederdissen, 2011-2013
homepage: http://www.tbi.univie.ac.at/~choener/adpfusion
maintainer: choener@tbi.univie.ac.at
category: Algorithms, Data Structures, Bioinformatics
license: BSD3
license-file: LICENSE
build-type: Simple
stability: experimental
cabal-version: >= 1.6.0
synopsis:
Efficient, high-level dynamic programming.
description:
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
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
().
.
Performance comparison figure:
.
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:
and
.
Extra-Source-Files:
README.md
changelog
library
build-depends:
base >= 4 && < 5,
deepseq >= 1.3 ,
ghc-prim ,
primitive >= 0.5 ,
PrimitiveArray == 0.5.2.* ,
QuickCheck >= 2.5 ,
repa >= 3.2 ,
strict >= 0.3.2 ,
template-haskell ,
transformers ,
vector >= 0.10
exposed-modules:
ADP.Fusion
ADP.Fusion.Apply
ADP.Fusion.Chr
ADP.Fusion.Classes
ADP.Fusion.Empty
ADP.Fusion.Examples.Palindrome
ADP.Fusion.Multi
ADP.Fusion.Multi.Classes
ADP.Fusion.Multi.Empty
ADP.Fusion.Multi.GChr
ADP.Fusion.Multi.None
ADP.Fusion.None
ADP.Fusion.QuickCheck
ADP.Fusion.Region
ADP.Fusion.Table
ADP.Fusion.TH
ghc-options:
-O2 -funbox-strict-fields
executable NeedlemanWunsch
main-is:
ADP/Fusion/Examples/TwoDim.hs
ghc-options:
-Odph
-funbox-strict-fields
-funfolding-use-threshold1000
-funfolding-keeness-factor1000
-fllvm
-optlo-O3 -optlo-std-compile-opts
-fllvm-tbaa
source-repository head
type: git
location: git://github.com/choener/ADPfusion