ADPfusion: Efficient, high-level dynamic programming

[Christian Höner zu Siederdissen-2]

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

_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users