Hackage :: [Package]

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

[ data-structures, library, mit ] [ Propose Tags ] [ Report a vulnerability ]

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.

[Skip to Readme]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1.0.0
Change log CHANGELOG.md
Dependencies 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]
Tested with ghc ==9.0.1
License MIT
Author Donnacha Oisín Kidney
Maintainer mail@doisinkidney.com
Category Data Structures
Home page https://github.com/oisdk/monus-weighted-search
Bug tracker https://github.com/oisdk/monus-weighted-search/issues
Source repo head: git clone git://github.com/oisdk/monus-weighted-search.git
Uploaded by oisdk at 2021-08-29T17:21:40Z
Distributions
Downloads 163 total (6 in the last 30 days)
Rating 2.0 (votes: 1) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]

Readme for monus-weighted-search-0.1.0.0

[back to package description]

monus-weighted-search

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

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.