Control.Monad.AStar

See the README for usage info and examples.

Types

type AStar s c r a = AStarT s c r Identity a

Non-transformer version of AStarT

data AStarT s c r m a

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)

Defined in Control.Monad.AStar

Methods

branch :: AStarT s w r m a -> AStarT s w r m a -> AStarT s w r m a

updateCost :: w -> AStarT s w r m ()

done :: r -> AStarT s w r m a

(Ord c, Monad m) => MonadState s (AStarT s c r m)

Defined in Control.Monad.AStar

Methods

get :: AStarT s c r m s

put :: s -> AStarT s c r m ()

state :: (s -> (a, s)) -> AStarT s c r m a

MonadTrans (AStarT s c r)

Defined in Control.Monad.AStar

Methods

lift :: Monad m => m a -> AStarT s c r m a

(Monad m, Ord c) => Monad (AStarT s c r m)

Defined in Control.Monad.AStar

Methods

(>>=) :: AStarT s c r m a -> (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 b

return :: a -> AStarT s c r m a

fail :: String -> AStarT s c r m a

Functor (AStarT s c r m)

Defined in Control.Monad.AStar

Methods

fmap :: (a -> b) -> AStarT s c r m a -> AStarT s c r m b

(<$) :: a -> AStarT s c r m b -> AStarT s c r m a

(Ord c, Monad m) => MonadFail (AStarT s c r m)

Defined in Control.Monad.AStar

Methods

fail :: String -> AStarT s c r m a

(Monad m, Ord c) => Applicative (AStarT s c r m)

Defined in Control.Monad.AStar

Methods

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)

Defined in Control.Monad.AStar

Methods

liftIO :: IO a -> AStarT s c r m a

(Ord c, Monad m) => Alternative (AStarT s c r m)

Defined in Control.Monad.AStar

Methods

empty :: AStarT s c r m a

(<|>) :: AStarT s c r m a -> AStarT s c r m a -> AStarT s c r m a

some :: AStarT s c r m a -> AStarT s c r m [a]

many :: AStarT s c r m a -> AStarT s c r m [a]

(Ord c, Monad m) => MonadPlus (AStarT s c r m)

Defined in Control.Monad.AStar

Methods

mzero :: AStarT s c r m a

mplus :: AStarT s c r m a -> AStarT s c r m a -> AStarT s c r m a

Methods

class MonadAStar w r m | m -> r, m -> w where

A class which represents the ability to do A* search.

Methods

branch :: m a -> m a -> m a

Branch the search

updateCost :: w -> m ()

Update the cost estimate of the current branch and re-evaluate available branches, switching to a cheaper one when appropriate.

done :: r -> m a

Return a solution and short-circuit any remaining branches.

Instances

(Ord w, Monad m) => MonadAStar w r (AStarT s w r m)

Defined in Control.Monad.AStar

Methods

branch :: AStarT s w r m a -> AStarT s w r m a -> AStarT s w r m a

updateCost :: w -> AStarT s w r m ()

done :: r -> AStarT s w r m a

Executing Search

runAStarT :: Monad m => AStarT s c r m a -> s -> m (Maybe (r, s))

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)

Run an effectful A* computation returning only the branch state

evalAStarT :: Monad m => AStarT s c r m a -> s -> m (Maybe r)

Run an effectful A* computation returning only the solution

runAStar :: AStar s c r a -> s -> Maybe (r, s)

Run a pure A* computation returning the solution and branch state if one was found.

execAStar :: AStar s c r a -> s -> Maybe s

Run a pure A* computation returning only the branch state

evalAStar :: AStar s c r a -> s -> Maybe r

Run a pure A* computation returning only the solution

tryWhile :: (c -> Bool) -> AStar s c r a -> s -> Maybe (r, s)

Run a pure A* search but short-circuit when the lowest cost fails a predicate.

This is useful for detecting if your search is diverging, or is likely to fail.

tryWhileT :: Monad m => (c -> Bool) -> AStarT s c r m a -> s -> m (Maybe (r, s))

Effectful version of tryWhile