Efficient search weighted by an ordered monoid with monus.

This package contains the Haskell constructions from the paper "Algebras for Weighted Search":

• Donnacha Oisín Kidney and Nicolas Wu. 2021. Algebras for weighted search. Proc. ACM Program. Lang. 5, ICFP, Article 72 (August 2021), 30 pages. DOI:https://doi.org/10.1145/3473577

In particular, it contains the HeapT monad, the Monus class, and the example uses of those types from the paper (see MonusWeightedSearch.Examples.Dijkstra, in particular).

The types given here have been tested and are implemented in a way that is intended to be usable in "real" code, although the primary purpose of this package is to demonstrate that the code in the paper does in fact function.

monus-weighted-search

This is a Haskell package containing the heap monad and some of the examples in the paper

• "Algebras for weighted search", Donnacha Oisín Kidney and Nicolas Wu. 2021. Proc. ACM Program. Lang. 5, ICFP, Article 72 (August 2021), 30 pages. DOI:https://doi.org/10.1145/3473577

It contains three main components:

• The Monus class (and some instances).
• The HeapT monad, as described in the last section of the paper.
• Examples using the HeapT monad.

The Monus class can be found in Data.Monus, HeapT is in Control.Monad.Heap, and the examples are in the MonusWeightedSearch.Examples directory.

The examples include:

• Dijkstra's algorithm (MonusWeightedSearch.Examples.Dijkstra)
• Probabilistic parsing (MonusWeightedSearch.Examples.Parsing)
• Probabilistic sampling (MonusWeightedSearch.Examples.Sampling)
• The Viterbi algorithm (MonusWeightedSearch.Examples.Viterbi)

Thought he primary purpose of this package is to demonstrate the ideas in the paper, the heap monad has been packaged so it can be used as-is in "real" code.

The documentation is compiled on every commit, it can be seen here.

Benchmarks are run occasionally, their output can be seen here.