{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T08:34:21Z","timestamp":1770280461371,"version":"3.49.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2021,8,19]],"date-time":"2021-08-19T00:00:00Z","timestamp":1629331200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/S028129\/1"],"award-info":[{"award-number":["EP\/S028129\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2021,8,22]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>The development first explores breadth-first search, which can be expressed as a polynomial over semirings. These polynomials are generalised to the free semimodule monad to capture a wide range of applications, including probability monads, polynomial monads, and monads for weighted search. Finally, a monad transformer based on the free semimodule 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.<\/jats:p>","DOI":"10.1145\/3473577","type":"journal-article","created":{"date-parts":[[2021,8,19]],"date-time":"2021-08-19T10:44:29Z","timestamp":1629369869000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Algebras for weighted search"],"prefix":"10.1145","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4952-7359","authenticated-orcid":false,"given":"Donnacha Ois\u00edn","family":"Kidney","sequence":"first","affiliation":[{"name":"Imperial College London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4161-985X","authenticated-orcid":false,"given":"Nicolas","family":"Wu","sequence":"additional","affiliation":[{"name":"Imperial College London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,8,19]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380190202"},{"key":"e_1_2_2_2_1","unstructured":"Thorsten Altenkirch Thomas Anberr\u00e9e and Nuo Li. 2011. Definable Quotients in Type Theory. http:\/\/www.cs.nott.ac.uk\/~psztxa\/publ\/defquotients.pdf  Thorsten Altenkirch Thomas Anberr\u00e9e and Nuo Li. 2011. Definable Quotients in Type Theory. http:\/\/www.cs.nott.ac.uk\/~psztxa\/publ\/defquotients.pdf"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01182254"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.TYPES.2018.1"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.153.2"},{"key":"e_1_2_2_6_1","article-title":"On the Theory of Groups as Depending on the Symbolic Equation $\u00fe eta$n= 1","author":"Cayley A.","year":"1854","journal-title":"Phil. Mag."},{"key":"e_1_2_2_7_1","volume-title":"Proceedings of the 7th IFIP Congress 1977","author":"Keith","year":"1977"},{"key":"e_1_2_2_8_1","unstructured":"Noah Easterly. 2019. Functions and Newtype Wrappers for Traversing Trees: Rampion\/Tree-Traversals. https:\/\/github.com\/rampion\/tree-traversals  Noah Easterly. 2019. Functions and Newtype Wrappers for Traversing Trees: Rampion\/Tree-Traversals. https:\/\/github.com\/rampion\/tree-traversals"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796801004075"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796805005721"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129509990351"},{"key":"e_1_2_2_12_1","volume-title":"Informatik","author":"Fischer Sebastian","year":"2009"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840439"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/289423.289455"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/165180.165214"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-0383-3_1"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.153.3"},{"key":"e_1_2_2_18_1","unstructured":"Ralf Hinze. 1999. Efficient Monadic-Style Backtracking. Sept. 51.  Ralf Hinze. 1999. Efficient Monadic-Style Backtracking. Sept. 51."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/351240.351258"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796805005769"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00165-012-0245-4"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90059-1"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796810000122"},{"key":"e_1_2_2_24_1","volume-title":"Basic Algebra I","author":"Jacobson Nathan","year":"1933","edition":"2"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.09.011"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2784731.2784743"},{"key":"e_1_2_2_27_1","volume-title":"Linear-Time Breadth-First Tree Algorithms: An Exercise in the Arithmetic of Folds and Zips. Dept of Computer Science","author":"Jones Geraint"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-59451-5_4"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.4774319"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199530"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1086365.1086390"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973198.7"},{"key":"e_1_2_2_33_1","volume-title":"Sauerwein","author":"Launchbury John","year":"2000"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796807006326"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796899003299"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01211391"},{"key":"e_1_2_2_37_1","first-page":"321","article-title":"Semiring Frameworks and Algorithms for Shortest-Distance Problems","volume":"7","author":"Mohri Mehryar","year":"2002","journal-title":"J. Autom. Lang. Comb."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/351240.351253"},{"key":"e_1_2_2_39_1","volume-title":"Mathematics of Program Construction, Jeremy Gibbons and Pablo Nogueira (Eds.) (Lecture Notes in Computer Science)","author":"Paterson Ross"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.207.2"},{"key":"e_1_2_2_41_1","unstructured":"Exequiel Rivas and Mauro Jaskelioff. 2014. Notions of Computation as Monoids. arXiv:1406.4823 [cs math] May arxiv:1406.4823. arxiv:1406.4823  Exequiel Rivas and Mauro Jaskelioff. 2014. Notions of Computation as Monoids. arXiv:1406.4823 [cs math] May arxiv:1406.4823. arxiv:1406.4823"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2017.09.007"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_2_2_44_1","first-page":"28","article-title":"Lloyd Allison\u2019s Corecursive Queues","volume":"14","author":"Smith Leon P","year":"2009","journal-title":"Why Continuations Matter. The Monad.Reader"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796809007321"},{"key":"e_1_2_2_46_1","doi-asserted-by":"crossref","unstructured":"J. Michael Spivey and Silvija Seres. 2003. Combinators for Logic Programming. In The Fun of Programming. Palgrave. https:\/\/www.cs.ox.ac.uk\/publications\/books\/fop\/dist\/fop\/chapters\/9\/Logic.hs  J. Michael Spivey and Silvija Seres. 2003. Combinators for Logic Programming. In The Fun of Programming. Palgrave. https:\/\/www.cs.ox.ac.uk\/publications\/books\/fop\/dist\/fop\/chapters\/9\/Logic.hs","DOI":"10.1007\/978-1-349-91518-7_9"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800003749"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897336.2897342"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341691"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70594-9_20"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-15975-4_33"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/91556.91592"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(92)90104-N"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3473577","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3473577","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:15Z","timestamp":1750195695000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3473577"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,19]]},"references-count":54,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2021,8,22]]}},"alternative-id":["10.1145\/3473577"],"URL":"https:\/\/doi.org\/10.1145\/3473577","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,19]]},"assertion":[{"value":"2021-08-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}