Publications

BibTex format

@article{Kidney:2021:10.1145/3473577,
author = {Kidney, DO and Wu, N},
doi = {10.1145/3473577},
journal = {Proceedings of the ACM on Programming Languages},
pages = {1--30},
title = {Algebras for weighted search},
url = {http://dx.doi.org/10.1145/3473577},
volume = {5},
year = {2021}
}

Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - Weighted search is an essential component of many fundamental and useful algorithms. Despite this, it is relatively under explored as a computational effect, receiving not nearly as much attention as either depth- or breadth-first search. This paper explores the algebraic underpinning of weighted search, and demonstrates how to implement it as a monad transformer. The development first explores breadth-first search, which can be expressed as a polynomial over semirings. These polynomials are generalised to the free semi module monad to capture a wide range of applications, including probability monads, polynomial monads, and monads for weighted search. Finally, a monad trans-former based on the free semi module monad is introduced. Applying optimisations to this type yields an implementation of pairing heaps, which is then used to implement Dijkstra’s algorithm and efficient probabilistic sampling. The construction is formalised in Cubical Agda and implemented in Haskell.
AU  - Kidney,DO
AU  - Wu,N
DO  - 10.1145/3473577
EP  - 30
PY  - 2021///
SN  - 2475-1421
SP  - 1
TI  - Algebras for weighted search
T2  - Proceedings of the ACM on Programming Languages
UR  - http://dx.doi.org/10.1145/3473577
UR  - https://dl.acm.org/doi/10.1145/3473577
UR  - http://hdl.handle.net/10044/1/90693
VL  - 5
ER  -

Download

DrNicolasWu

Contact

Location

Summary

Citation

BibTex format

RIS format (EndNote, RefMan)