Copyright | (c) Chris Penner 2019 |
---|---|
License | BSD3 |
Safe Haskell | Safe |
Language | Haskell2010 |
See the README for usage info and examples.
Synopsis
- type AStar s c r a = AStarT s c r Identity a
- data AStarT s c r m a
- class MonadPlus m => MonadAStar w r m | m -> r, m -> w where
- updateCost :: w -> m ()
- done :: r -> m a
- branch :: MonadAStar w r m => m a -> m a -> m a
- failure :: MonadAStar w r m => m a
- runAStarT :: Monad m => AStarT s c r m a -> s -> m (Maybe (r, s))
- execAStarT :: Monad m => AStarT s c r m a -> s -> m (Maybe s)
- evalAStarT :: Monad m => AStarT s c r m a -> s -> m (Maybe r)
- runAStar :: AStar s c r a -> s -> Maybe (r, s)
- execAStar :: AStar s c r a -> s -> Maybe s
- evalAStar :: AStar s c r a -> s -> Maybe r
- tryWhile :: (c -> Bool) -> AStar s c r a -> s -> Maybe (r, s)
- tryWhileT :: Monad m => (c -> Bool) -> AStarT s c r m a -> s -> m (Maybe (r, s))
Types
data AStarT s c r m a Source #
The AStar
search monad transformer
Lots of type variables here:
s
: State; keep anything you want in here, it will stay coherent across
branch switches.
c
: Cost measure: The type you'll use for determining the estimated cost of following a given
branch. Usually requires Ord
.
r
: Result type, this is often redundant to State but is provided for convenience.
This is the type you pass to done
when you've found a solution.
m
: An arbitrary monad which will be threaded through.
Be wary that effects will be run in seemingly non-deterministic ordering as we switch chaotically between branches.
Instances
(Ord w, Monad m) => MonadAStar w r (AStarT s w r m) Source # | |
Defined in Control.Monad.AStar | |
(Ord c, Monad m) => MonadState s (AStarT s c r m) Source # | |
MonadTrans (AStarT s c r) Source # | |
Defined in Control.Monad.AStar | |
(Monad m, Ord c) => Monad (AStarT s c r m) Source # | |
Functor (AStarT s c r m) Source # | |
(Ord c, Monad m) => MonadFail (AStarT s c r m) Source # | |
Defined in Control.Monad.AStar | |
(Monad m, Ord c) => Applicative (AStarT s c r m) Source # | |
Defined in Control.Monad.AStar pure :: a -> AStarT s c r m a # (<*>) :: AStarT s c r m (a -> b) -> AStarT s c r m a -> AStarT s c r m b # liftA2 :: (a -> b -> c0) -> AStarT s c r m a -> AStarT s c r m b -> AStarT s c r m c0 # (*>) :: AStarT s c r m a -> AStarT s c r m b -> AStarT s c r m b # (<*) :: AStarT s c r m a -> AStarT s c r m b -> AStarT s c r m a # | |
(MonadIO m, Ord c) => MonadIO (AStarT s c r m) Source # | |
Defined in Control.Monad.AStar | |
(Ord c, Monad m) => Alternative (AStarT s c r m) Source # | |
(Ord c, Monad m) => MonadPlus (AStarT s c r m) Source # | |
Methods
class MonadPlus m => MonadAStar w r m | m -> r, m -> w where Source #
A class which represents the ability to do A* search.
The laws aren't completely pinned down yet, but these should probably hold:
It should short-circuit on 'done' done a >> mx == done a done a <|> mx == done a It should fail a branch using `empty`. empty >> mx == empty empty <|> mx == mx It should branch respecting costs using `<|>` from its 'Alternative' instance. (updateCost 2 >> mx) <|> (updateCost 1 >> my) == mx <|> my
updateCost :: w -> m () Source #
Update the cost estimate of the current branch and re-evaluate available branches, switching to a cheaper one when appropriate.
Return a solution and short-circuit any remaining branches.
Instances
(Ord w, Monad m) => MonadAStar w r (AStarT s w r m) Source # | |
Defined in Control.Monad.AStar |
branch :: MonadAStar w r m => m a -> m a -> m a Source #
Branch the search.
branch == (<|>)
failure :: MonadAStar w r m => m a Source #
Fail the current branch.
branch == empty
Executing Search
runAStarT :: Monad m => AStarT s c r m a -> s -> m (Maybe (r, s)) Source #
Run an A* computation effect returning the solution and branch state if one was found.
execAStarT :: Monad m => AStarT s c r m a -> s -> m (Maybe s) Source #
Run an effectful A* computation returning only the branch state
evalAStarT :: Monad m => AStarT s c r m a -> s -> m (Maybe r) Source #
Run an effectful A* computation returning only the solution
runAStar :: AStar s c r a -> s -> Maybe (r, s) Source #
Run a pure A* computation returning the solution and branch state if one was found.
execAStar :: AStar s c r a -> s -> Maybe s Source #
Run a pure A* computation returning only the branch state
evalAStar :: AStar s c r a -> s -> Maybe r Source #
Run a pure A* computation returning only the solution