ADPfusion: Efficient, high-level dynamic programming

Christian Höner zu Siederdissen choener 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)


1st example program:

Many thanks to Roman Leshchinskiy!

Viele Gruesse,
Christian Hoener zu Siederdissen

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: not available
URL: <>

More information about the Glasgow-haskell-users mailing list