monad-dijkstra: A monad transformer for weighted graph searches

[ bsd3, control, library, monads ] [ Propose Tags ]

A monad transformer for weighted graph searches using Dijkstra's or A* algorithm.


[Skip to Readme]

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

Versions [RSS] 0.1.0.0, 0.1.1.0, 0.1.1.1, 0.1.1.2, 0.1.1.3, 0.1.1.4, 0.1.1.5
Change log CHANGELOG.md
Dependencies base (>=4.7 && <5), containers (>=0.5.6.2 && <0.8), free (>=4.12.0 && <5.3), mtl (>=2.2.0 && <2.4), psqueues (>=0.2.0.0 && <0.3), transformers (>=0.4.2.0 && <0.7) [details]
License BSD-3-Clause
Copyright Copyright (c) 2016-2023 Enno Cramer
Author Enno Cramer
Maintainer Enno Cramer <ecramer@memfrob.de>
Category Control, Monads
Home page https://github.com/ennocramer/monad-dijkstra
Source repo head: git clone https://github.com/ennocramer/monad-dijkstra
Uploaded by ecramer at 2023-12-18T09:10:04Z
Distributions Arch:0.1.1.5, NixOS:0.1.1.5
Reverse Dependencies 2 direct, 2 indirect [details]
Downloads 13363 total (167 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2023-12-18 [all 1 reports]

Readme for monad-dijkstra-0.1.1.5

[back to package description]

monad-dijkstra

Hackage Build Status License

A monad transformer for weighted graph searches using Dijkstra's or A* algorithm.

The SearchT Monad Transformer

This library implements the SearchT monad transformer, in which monadic computations can be associated with costs and alternative computational paths can be explored concurrently. The API is built in terms of the Alternative and MonadPlus type classes and a cost function.

The runSearch function lazily evaluates all alternative computations, returning non-empty solutions in order of increasing cost. When forcing only the head of the result list, the function performs the minimal amount of work necessary to guarantee the optimal solution, i.e. with the least cost, is returned first.

The runSearchT function will also evaluate all alternatice computations in order of increasing cost, but the resulting list will likely not be lazy, depending bind operation of the underlying monad. The collapse function can be used to terminate the search when all interesting solutions have been found.

Computational Cost

The cost of a computation is set using the cost function. Repeated calls within a branch of computation will accumulate the cost using mappend from the type's Monoid instance. In addition to the computational cost expended, the cost function also accepts a cost estimate for the rest of computation. Subsequent calls to cost will reset this estimate.

Limitations

Any type that satisfies the Monoid and Ord type classes may be used as a cost values. However, the internal evaluation algorithm requires that costs not be negative. That is, for any costs a and b, a <> b >= a && a <> b >= b.

For the runSearchT function to generate solutions in the correct order, estimates must never overestimate the cost of a computation. If the cost of a branch is over-estimated or a negative cost is applied, runSearchT may return results in the wrong order.

Usage Example

type Location = ...
type Distance = ...

distance :: Location -> Location -> Distance
distance = ...

neighbors :: Location -> [(Location, Distance)]
neighbors = ...

shortedtRoute :: Location -> Location -> Maybe (Distance, [Location])
shortestRoute from to = listToMaybe $ runSearch $ go [from]
  where
    go ls = if head ls == to
               then return ls
               else msum $ flip map (neighbors (head ls)) $
                   \(l, d) -> cost d (distance l to) $ go (l : ls)