# monus-weighted-search: Efficient search weighted by an ordered monoid with monus.

[ data-structures, library, mit ] [ Propose Tags ]

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.

#### Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

• No Candidates
Versions [RSS] 0.1.0.0 CHANGELOG.md array (>=0.5), base (>=4.13 && <5), containers (>=0.1.0.0), deepseq (>=1.1), mtl (>=2.2), QuickCheck (>=2.10), random (>=1.0), transformers (>=0.4.2) [details] MIT Donnacha Oisín Kidney mail@doisinkidney.com Data Structures https://github.com/oisdk/monus-weighted-search https://github.com/oisdk/monus-weighted-search/issues head: git clone git://github.com/oisdk/monus-weighted-search.git by oisdk at 2021-08-29T17:21:40Z NixOS:0.1.0.0 88 total (8 in the last 30 days) 2.0 (votes: 1) [estimated by Bayesian average] λ λ λ Docs uploaded by userBuild status unknown

[back to package description]

# 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.