monad-dijkstra 0.1.1.4 → 0.1.1.5

raw patch · 3 files changed

+117/−2 lines, 3 filesdep ~containersPVP ok

version bump matches the API change (PVP)

Dependency ranges changed: containers

API changes (from Hackage documentation)

Files

• CHANGELOG.md +34/−0
• README.md +77/−0
• monad-dijkstra.cabal +6/−2

@@ -0,0 +1,34 @@+# monad-dijkstra 0.1.1.5++* Support for containers-0.7.0.0++# monad-dijkstra 0.1.1.4++* Support GHC-9.0+* Support GHC-9.2+* Support GHC-9.4+* Support GHC-9.6++# monad-dijkstra 0.1.1.3++* Removed unused language pragma+* Support GHC-8.6.3 and Stackage LTS-16+* Support GHC-8.8.3+* Support GHC-8.10.1++# monad-dijkstra 0.1.1.2++* Performance improvements++# monad-dijkstra 0.1.1.1++* Support GHC-8.4.4 and Stackage LTS-12++# monad-dijkstra 0.1.1.0++* Add functions runSearchBest and runSearchBestT+* Improve documentation for runSearchT in strict sequencing monads like IO++# monad-dijkstra 0.1.0.0++* Initial release

@@ -0,0 +1,77 @@+# monad-dijkstra++[![Hackage][hackage-image]][hackage-url]+[![Build Status][ci-image]][ci-url]+[![License][license-image]][license-url]++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++```haskell+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)+```+<!-- Markdown link & img dfn's -->+[hackage-image]: https://img.shields.io/hackage/v/monad-dijkstra.svg?style=flat+[hackage-url]: https://hackage.haskell.org/package/monad-dijkstra+[ci-image]: https://github.com/ennocramer/monad-dijkstra/workflows/CI%20Pipeline/badge.svg+[ci-url]: https://github.com/ennocramer/monad-dijkstra/actions?query=workflow%3A%22CI+Pipeline%22+[license-image]: https://img.shields.io/badge/license-BSD--3--Clause-blue?style=flat-square+[license-url]: https://github.com/ennocramer/monad-dijkstra/blob/master/LICENSE.md

@@ -1,6 +1,6 @@ cabal-version: >=1.10 name:          monad-dijkstra-version:       0.1.1.4+version:       0.1.1.5 license:       BSD3 license-file:  LICENSE copyright:     Copyright (c) 2016-2023 Enno Cramer@@ -14,6 +14,10 @@ category:      Control, Monads build-type:    Simple +extra-source-files:+    README.md+    CHANGELOG.md+ source-repository head     type:     git     location: https://github.com/ennocramer/monad-dijkstra@@ -25,7 +29,7 @@     ghc-options:      -Wall     build-depends:         base >=4.7 && <5,-        containers >=0.5.6.2 && <0.7,+        containers >=0.5.6.2 && <0.8,         transformers >=0.4.2.0 && <0.7,         mtl >=2.2.0 && <2.4,         free >=4.12.0 && <5.3,