[Haskell] ADPfusion: Efficient, high-level dynamic programming

Christian Höner zu Siederdissen choener at tbi.univie.ac.at
Sun Mar 25 03:57:42 CEST 2012

ADPfusion combines stream-fusion (using the stream interface provided by
the vector library) and type-level programming to provide highly
efficient dynamic programming (DP) combinators.

You can write DP programs in a style similar to Algebraic Dynamic
Programming (ADP) (Giegerich et al.), meaning symbolically without
explicit indices. The symbolic operators provide a number of advantages:

- take care of extracting the correct cell information from data
  structures (DP matrices)
- no more index problems, the grammars are completely free of index
  calculations by the user
- complex operators can be written with "next step" behaviour dependent
  on other information calculated during runtime
- monadic interface
- works with pure/monadic, boxed/unboxed, ... data structures
- speed close to optimized C (between 1.8x - 3x slower currently --
  compared to well-optimized C-code)

Hackage: http://hackage.haskell.org/package/ADPfusion

1st example program: http://hackage.haskell.org/package/Nussinov78

Many thanks to Roman Leshchinskiy!

Viele Gruesse,
Christian Hoener zu Siederdissen

ADP: http://bibiserv.techfak.uni-bielefeld.de/adp/adpapp.html
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell/attachments/20120325/24f8cebc/attachment.pgp>

More information about the Haskell mailing list