A monad for implemented bounded depth-first-search and branch-and-bound search.
- class Monad m => MonadCost c m | m -> c where
- updateCost :: (c -> c) -> m ()
- newtype UnboundedDFS c a = UnboundedDFS {
- runUnboundedDFS :: Maybe a
- newtype BoundedDFS c a = BoundedDFS {
- unBoundedDFS :: ReaderT (c -> Bool) (StateT c Maybe) a
- runBoundedDFS :: BoundedDFS c a -> (c -> Bool) -> c -> Maybe (a, c)
- evalBoundedDFS :: BoundedDFS c a -> (c -> Bool) -> c -> Maybe a
- execBoundedDFS :: BoundedDFS c a -> (c -> Bool) -> c -> Maybe c
- newtype BranchAndBound c a = BranchAndBound {
- unBranchAndBound :: ReaderT (c -> Bool) (StateT c Maybe) a
- runBranchAndBound :: Cost c => BranchAndBound c a -> c -> Maybe (a, c)
- evalBranchAndBound :: Cost c => BranchAndBound c a -> c -> Maybe a
- execBranchAndBound :: Cost c => BranchAndBound c a -> c -> Maybe c
Costful operations
class Monad m => MonadCost c m | m -> c whereSource
A monad with integer operation cost recording.
updateCost :: (c -> c) -> m ()Source
Mark the cost of the current operation.
MonadCost c (BranchAndBound c) | |
MonadCost c (BoundedDFS c) | |
MonadCost c (UnboundedDFS c) |
Unbounded depth-first-search
newtype UnboundedDFS c a Source
An unbounded depth-first search monad for searches formulated using MonadPlus.
MonadCost c (UnboundedDFS c) | |
Monad (UnboundedDFS c) | |
MonadPlus (UnboundedDFS c) |
Bounded depth-first-search
newtype BoundedDFS c a Source
A cost bounded depth-first search monad.
All choices are handled committing and there is no differentiation between failure due to cost overrun and other failures.
BoundedDFS | |
|
MonadCost c (BoundedDFS c) | |
Monad (BoundedDFS c) | |
MonadPlus (BoundedDFS c) |
runBoundedDFS :: BoundedDFS c a -> (c -> Bool) -> c -> Maybe (a, c)Source
Run a cost bounded depth-first search.
evalBoundedDFS :: BoundedDFS c a -> (c -> Bool) -> c -> Maybe aSource
Evaluate a cost bounded depth-first search.
execBoundedDFS :: BoundedDFS c a -> (c -> Bool) -> c -> Maybe cSource
Execute a cost bounded depth-first search.
Branch-and-bound search
newtype BranchAndBound c a Source
A branch and bound monad for finding results with the smallest costs.
BranchAndBound | |
|
MonadCost c (BranchAndBound c) | |
Monad (BranchAndBound c) | |
Cost c => MonadPlus (BranchAndBound c) |
runBranchAndBound :: Cost c => BranchAndBound c a -> c -> Maybe (a, c)Source
Run a branch and bound search.
evalBranchAndBound :: Cost c => BranchAndBound c a -> c -> Maybe aSource
Evaluate a branch and bound search.
execBranchAndBound :: Cost c => BranchAndBound c a -> c -> Maybe cSource
Execute a branch and bound search.