Control.Monad.AStar.Class

Documentation

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

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

Methods

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

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

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

branch :: MonadAStar w r m => m a -> m a -> m a

Branch the search.

branch == (<|>)

failure :: MonadAStar w r m => m a

Fail the current branch.

branch == empty