{-# 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