ADPfusion: Efficient, high-level dynamic programming.

[ algorithms, bioinformatics, bsd3, data-structures, formal-languages, library ] [ Propose Tags ]

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

ADPfusion allows writing dynamic programs for single- and multi-tape problems. Inputs can be sequences, or sets. And new input types can be defined, without having to rewrite this library thanks to the open-world assumption of ADPfusion.

The library provides the machinery for Outside and Ensemble algorithms as well. Ensemble algorithms combine Inside and Outside calculations.

The homepage provides a number of tutorial-style examples, with linear and context-free grammars over sequence and set inputs.

Ideas implemented here are described in a couple of papers:

Christian Hoener zu Siederdissen
Sneaking Around ConcatMap: Efficient Combinators for Dynamic Programming
2012. Proceedings of the 17th ACM SIGPLAN international conference on Functional programming preprint:
Andrew Farmer, Christian Höner zu Siederdissen, and Andy Gill.
The HERMIT in the stream: fusing stream fusion’s concatMap.
2014. Proceedings of the ACM SIGPLAN 2014 workshop on Partial evaluation and program manipulation.
Christian Höner zu Siederdissen, Ivo L. Hofacker, and Peter F. Stadler.
Product Grammars for Alignment and Folding.
2014. IEEE/ACM Transactions on Computational Biology and Bioinformatics. 99.
Christian Höner zu Siederdissen, Sonja J. Prohaska, and Peter F. Stadler.
Algebraic Dynamic Programming over General Data Structures.
2015. submitted.

[Skip to Readme]
Versions [faq],,,,,,,,,,,,,,,,,,, (info)
Change log
Dependencies base (>=4.7 && <4.9), bits (==0.4.*), mmorph (==1.0.*), monad-primitive (==0.1), mtl (==2.*), OrderedBits (==0.0.0.*), primitive (>=0.5.4 && <0.7), PrimitiveArray (==0.6.0.*), QuickCheck (>=2.7 && <2.9), strict (==0.3.*), template-haskell (==2.*), transformers (>=0.3 && <0.5), tuple (==0.3.*), vector (==0.10.*) [details]
License BSD-3-Clause
Copyright Christian Hoener zu Siederdissen, 2011-2015
Author Christian Hoener zu Siederdissen, 2011-2015
Category Algorithms, Data Structures, Bioinformatics, Formal Languages
Home page
Source repo head: git clone git://
Uploaded by ChristianHoener at 2015-05-07T14:35:40Z
Distributions NixOS:
Executables Durbin, PartNussinov, Nussinov, NeedlemanWunsch
Downloads 15897 total (414 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs not available [build log]
All reported builds failed as of 2016-12-09 [all 7 reports]


  • ADP
    • ADP.Fusion
      • ADP.Fusion.Apply
      • ADP.Fusion.Base
        • ADP.Fusion.Base.Classes
        • ADP.Fusion.Base.Multi
        • ADP.Fusion.Base.Point
        • ADP.Fusion.Base.Set
        • ADP.Fusion.Base.Subword
      • QuickCheck
        • ADP.Fusion.QuickCheck.Common
        • ADP.Fusion.QuickCheck.Point
        • ADP.Fusion.QuickCheck.Set
        • ADP.Fusion.QuickCheck.Subword
      • ADP.Fusion.SynVar
        • ADP.Fusion.SynVar.Array
          • ADP.Fusion.SynVar.Array.Point
          • ADP.Fusion.SynVar.Array.Set
          • ADP.Fusion.SynVar.Array.Subword
          • ADP.Fusion.SynVar.Array.Type
        • ADP.Fusion.SynVar.Axiom
        • ADP.Fusion.SynVar.Backtrack
        • ADP.Fusion.SynVar.Fill
        • ADP.Fusion.SynVar.Indices
        • ADP.Fusion.SynVar.Recursive
          • ADP.Fusion.SynVar.Recursive.Point
          • ADP.Fusion.SynVar.Recursive.Subword
          • ADP.Fusion.SynVar.Recursive.Type
      • ADP.Fusion.TH
        • ADP.Fusion.TH.Backtrack
        • ADP.Fusion.TH.Common
      • ADP.Fusion.Term
        • ADP.Fusion.Term.Chr
          • ADP.Fusion.Term.Chr.Point
          • ADP.Fusion.Term.Chr.Subword
          • ADP.Fusion.Term.Chr.Type
        • ADP.Fusion.Term.Deletion
          • ADP.Fusion.Term.Deletion.Point
          • ADP.Fusion.Term.Deletion.Type
        • ADP.Fusion.Term.Edge
          • ADP.Fusion.Term.Edge.Set
          • ADP.Fusion.Term.Edge.Type
        • ADP.Fusion.Term.Epsilon
          • ADP.Fusion.Term.Epsilon.Point
          • ADP.Fusion.Term.Epsilon.Subword
          • ADP.Fusion.Term.Epsilon.Type
        • PeekIndex
          • ADP.Fusion.Term.PeekIndex.Subword
          • ADP.Fusion.Term.PeekIndex.Type
        • ADP.Fusion.Term.Strng
          • ADP.Fusion.Term.Strng.Point
          • ADP.Fusion.Term.Strng.Type



build the examples


build using LLVM


dump intermediate Core files


Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info


Maintainer's Corner

For package maintainers and hackage trustees

Readme for ADPfusion-

[back to package description]


Build Status

generalized ADPfusion Homepage


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 an example, even rather 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.

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.

Two algorithms from the realm of computational biology are provided as examples on how to write dynamic programming algorithms using this library: and


If GHC-7.2.2/GHC-7.4, LLVM and cabal-install are available, you should be all set. I recommend using cabal-dev as it provides a very nice sandbox (replace cabal-dev with cabal otherwise).

If you go with cabal-dev, no explicit installation is necessary and ADPfusion will be installed in the sandbox together with the example algorithms or your own.

For a more global installation, "cabal install ADPfusion" should do the trick.

To run the Quickcheck tests, do an additional "cabal-dev install QuickCheck", then "cabal-dev ghci", ":l ADP/Fusion/QuickCheck.hs", and "allProps". Loading the quickcheck module should take a bit due to compilation. "allProps" tests all properties and should yield no errors.


If you have problems, find bugs, or want to use this library to write your own DP algorithms, please send me a mail. I'm very interested in hearing what is missing.

One of the things I'll be integrating is an extension to higher dimensions (more than two).

Right now, I am not quite happy with the construction and destruction of the "Box" representations. These will change soon. In addition, an analysis of the actual combinators should remove the need for nested applications of objective functions in many cases.

Implementors Notes

  • The general inlining scheme is: (i) mkStream is {-# INLINE mkStream #-}, inner functions like mk, step, worker functions, and index-modifying functions get an {-# INLINE [0] funName #-}. Where there is no function to annotate, use delay_inline.

  • If you implement a new kind of memoizing table, like the dense Table.Array ones, you will have to implement mkStream code. When you hand to the left, the (i,j) indices and modify their extend (by, say, having NonEmpty table constaints), you have to delay_inline this (until inliner phase 0). Otherwise you will break fusion for mkStream.


Christian Hoener zu Siederdissen Leipzig University, Leipzig, Germany