@hackage ADPfusion0.6.0.0

Efficient, high-level dynamic programming.

  • Installation

  • Tested Compilers

  • Dependencies (20)

  • Dependents (15)

    @hackage/WordAlignment, @hackage/Forestry, @hackage/Gene-CluEDO, @hackage/FormalGrammars, @hackage/GrammarProducts, @hackage/RNAFold, Show all…

    • Package Flags

      debug
       (off by default)

      Enable bounds checking and various other debug operations at the cost of a significant performance penalty.

      debugoutput
       (off by default)

      Enable debug output, which spams the screen full of index information

      debugdump
       (off by default)

      Enable dumping intermediate / core files

      dump-core
       (off by default)

      Dump HTML for the core generated by GHC during compilation

      examples
       (off by default)

      build the examples

      spectest
       (off by default)

      build the spec-ctor test case

      devel
       (off by default)

      build additional tests

      btstruc
       (off by default)

      performance test for backtracking structures

      llvm
       (off by default)

      use llvm

generalized Algebraic 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. 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.

Starting with version 0.4.1 we support writing multiple context-free grammars (interleaved syntactic variables). Such grammars have applications in bioinformatics and linguistics.

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

The formal background for generalized algebraic dynamic programming and ADPfusion is described in a number of papers. These can be found on the gADP homepage and in the README.

Note: The core ADPfusion library only provides machinery for linear language over sequences. The add-ons ADPfusionSubword, ADPfusionForest, and others provide specialized machinery for other types of formal languages.