14
IRUS Total
Downloads

Algebras for weighted search

File Description SizeFormat 
3473577.pdfPublished version364.17 kBAdobe PDFView/Open
Title: Algebras for weighted search
Authors: Kidney, DO
Wu, N
Item Type: Journal Article
Abstract: 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.
Issue Date: 18-Aug-2021
Date of Acceptance: 19-Jun-2021
URI: http://hdl.handle.net/10044/1/90693
DOI: 10.1145/3473577
ISSN: 2475-1421
Publisher: Association for Computing Machinery (ACM)
Start Page: 1
End Page: 30
Journal / Book Title: Proceedings of the ACM on Programming Languages
Volume: 5
Copyright Statement: © 2021 Copyright held by the owner/author(s). This work is licensed under a Creative Commons Attribution 4.0 International License.
Sponsor/Funder: Engineering & Physical Science Research Council (EPSRC)
Funder's Grant Number: EP/S028129/1
Keywords: Science & Technology
Technology
Computer Science, Software Engineering
Computer Science
Haskell
Agda
graph search
monad
Science & Technology
Technology
Computer Science, Software Engineering
Computer Science
Haskell
Agda
graph search
monad
MONAD TRANSFORMERS
BACKTRACKING
Publication Status: Published
Article Number: 72
Online Publication Date: 2021-08-18
Appears in Collections:Computing
Faculty of Engineering



This item is licensed under a Creative Commons License Creative Commons