monad-dijkstra 0.1.0.0 → 0.1.1.0

raw patch · 3 files changed

+44/−15 lines, 3 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• monad-dijkstra.cabal +1/−1
• src/Control/Monad/Search.hs +17/−1
• test/Main.hs +26/−13

@@ -1,5 +1,5 @@ name:                monad-dijkstra-version:             0.1.0.0+version:             0.1.1.0 synopsis:            Monad transformer for weighted graph searches using Dijkstra's or A* algorithm description:         Please see README.md homepage:            https://github.com/ennocramer/monad-dijkstra

@@ -19,6 +19,12 @@ -- cost of a computation is overestimated or a negative cost is -- applied, sub-optimal solutions may be produced first. --+-- Note that while 'runSearchT' will produce a lazy list of results+-- and the computation space is only explored as far as the list is+-- forced, using 'runSearchT' with e.g. the 'IO' base monad will not.+-- You need to use 'collapse' or 'abandon' to prune the search space+-- within the monadic computation.+-- -- Example: -- -- > import Control.Monad.Search@@ -39,9 +45,11 @@     ( -- * The Search monad       Search     , runSearch+    , runSearchBest       -- * The SearchT monad transformer     , SearchT     , runSearchT+    , runSearchBestT       -- * MonadClass and search monad operations     , MonadSearch     , cost@@ -77,7 +85,7 @@                                              , runExceptT ) import           Control.Monad.Cont          ( MonadCont ) import           Data.Functor.Identity       ( Identity, runIdentity )-import           Data.Maybe                  ( catMaybes )+import           Data.Maybe                  ( catMaybes, listToMaybe )  import qualified Data.OrdPSQ                 as PSQ @@ -88,6 +96,10 @@ runSearch :: (Ord c, Monoid c) => Search c a -> [(c, a)] runSearch = runIdentity . runSearchT +-- | Generate only the best solution.+runSearchBest :: (Ord c, Monoid c) => Search c a -> Maybe (c, a)+runSearchBest = runIdentity . runSearchBestT+ -- | Functor for the Free monad SearchT data SearchF c a = Cost c c a                  | Alt a a@@ -179,6 +191,10 @@     state = St 0 0 queue      queue = PSQ.singleton 0 mempty (Cand mempty [ 0 ] (unSearchT m))++-- | Generate only the best solutions.+runSearchBestT :: (Ord c, Monoid c, Monad m) => SearchT c m a -> m (Maybe (c, a))+runSearchBestT m = listToMaybe <$> runSearchT (m <* collapse)  -- | Minimal definition is @cost@, @junction@, and @abandon@. class (Ord c, Monoid c, Monad m) => MonadSearch c m | m -> c where

@@ -19,9 +19,12 @@ testSearch :: Search C Side -> [(C, Side)] testSearch = runSearch -testSearchIO :: SearchT C IO Side -> IO [(C, Side)]-testSearchIO = runSearchT+testSearchIO :: SearchT C IO Side -> IO (Maybe (C, Side))+testSearchIO = runSearchBestT +infiniteSearch :: Monad m => SearchT C m Side+infiniteSearch = return L `mplus` (cost' (C 1) >> infiniteSearch)+ spec :: IO TestTree spec = testSpec "Control.Monad.Search" $ do     it "Monad return generates one result" $@@ -56,21 +59,31 @@      it "Results are generated lazily" $ do         head (testSearch (return L `mplus`-                              (cost' (C 1) >> return (error "not lazy right"))))+                              (cost' (C 1) >> error "not lazy right")))             `shouldBe` (C 0, L)-        head (testSearch ((cost' (C 1) >> return (error "not lazy left")) `mplus`-                              return L))+        head (testSearch ((cost' (C 1) >> error "not lazy left") `mplus`+                              return R))+            `shouldBe` (C 0, R)++    it "Results are generated lazily (infinite)" $+        head (testSearch infiniteSearch)             `shouldBe` (C 0, L) +    it "Results are generated in constant space / linear time" $+        testSearch infiniteSearch !! 10000+            `shouldBe` (C 10000, L)+     it "Results are generated lazily in IO" $ do-        head <$>-            testSearchIO (return L `mplus`-                              (cost' (C 1) >> return (error "not lazy right")))-                `shouldReturn` (C 0, L)-        head <$>-            testSearchIO ((cost' (C 1) >> return (error "not lazy left")) `mplus`-                              return L)-                `shouldReturn` (C 0, L)+        testSearchIO (return L `mplus`+                         (cost' (C 1) >> error "not lazy right"))+            `shouldReturn` Just (C 0, L)+        testSearchIO ((cost' (C 1) >> error "not lazy left") `mplus`+                         return R)+                `shouldReturn` Just (C 0, R)++    it "Results are generated lazily in IO (infinite)" $+        testSearchIO infiniteSearch+            `shouldReturn` Just (C 0, L)  main :: IO () main = do