An implementation of Dijkstra's algorithm, using the HeapT monad.

This is taken from section 6.1.3 of the paper

• 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

This is a pretty simple implementation of the algorithm, defined monadically, but it retains the time complexity of a standard purely functional implementation.

We use the state monad here to avoid searching from the same node more than once (which would lead to an infinite loop). Different algorithms use different permutations of the monad transformers: for Dijkstra's algorithm, we use HeapT w (State (Set a)) a, i.e. the HeapT is outside of the State. This means that each branch of the search proceeds with a different state; if we switch the order (to StateT s (Heap w) a, for example), we get "global" state, which has the semantics of a parser. For an example of that, see the module MonusWeightedSearch.Examples.Parsing, where the heap is used to implement a probabilistic parser.

>>> import Prelude hiding (head)
>>> import Data.List.NonEmpty (head)