{-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE FunctionalDependencies #-} module Control.Monad.AStar.Class (MonadAStar(..), branch, failure) where import Control.Monad import Control.Applicative -- | 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 class (MonadPlus m, Monoid c) => MonadAStar c r m | m -> r, m -> c where -- | ADD to your current branch's CUMULATIVE cost. May cause a branch switch. spend :: c -> m () -- | SET the current branch's BEST-CASE-COST cost. May cause a branch switch. estimate :: c -> m () -- | Return a solution and short-circuit any remaining branches. done :: r -> m a -- | Branch the search. -- -- > branch == (<|>) branch :: MonadAStar c r m => m a -> m a -> m a branch = (<|>) -- | Fail the current branch. -- -- > branch == empty failure :: MonadAStar c r m => m a failure = empty