# ADPfusion: Efficient, high-level dynamic programming.

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 http://doi.acm.org/10.1145/2364527.2364559 preprint: http://www.tbi.univie.ac.at/newpapers/pdfs/TBI-p-2012-2.pdf

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. http://dl.acm.org/citation.cfm?doid=2543728.2543736

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. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6819790

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] | 0.0.1.0, 0.0.1.1, 0.0.1.2, 0.1.0.0, 0.2.0.0, 0.2.0.1, 0.2.0.2, 0.2.0.3, 0.2.0.4, 0.2.1.0, 0.4.0.0, 0.4.0.1, 0.4.0.2, 0.4.1.0, 0.4.1.1, 0.5.0.0, 0.5.1.0, 0.5.2.0, 0.5.2.2, 0.6.0.0 (info) |
---|---|

Change log | changelog.md |

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 |

Maintainer | choener@bioinf.uni-leipzig.de |

Category | Algorithms, Data Structures, Bioinformatics, Formal Languages |

Home page | http://www.bioinf.uni-leipzig.de/Software/gADP/ |

Source repo | head: git clone git://github.com/choener/ADPfusion |

Uploaded | by ChristianHoener at 2015-05-07T14:35:40Z |

Distributions | NixOS:0.6.0.0 |

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 | Docs not available [build log] All reported builds failed as of 2016-12-09 [all 7 reports] |

## Modules

*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.SynVar.Array
- 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

- ADP.Fusion.Term.Chr

- ADP.Fusion

## Flags

Name | Description | Default | Type |
---|---|---|---|

examples | build the examples | Disabled | Manual |

llvm | build using LLVM | Disabled | Manual |

debug | dump intermediate Core files | Disabled | Manual |

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

## Downloads

- ADPfusion-0.4.0.0.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)