holmes-0.3.0.1: Tools and combinators for solving constraint problems.

Description

MoriarT is a monad transformer implementing the MonadCell class with provenance and backtracking search. In other words, it can search large parameter spaces using different parameter configurations, looking for contradicting sets of parameters to prune out parts of the search tree. It does this by keeping track of which cells influence which results, and considering any influencers on a failure to be contradictory.

In other words: if a write to cell A fails, and the write was based on values from cells B and C, any search branch in which B and C have these current values will be pruned from the search, and we won't try them.

(In practice, this isn't strictly true: we just abort any branch that ever produces any cell with any provenance that contains those values for B and C. This is a "lazier" strategy, and doesn't involve evaluating the search space up front).

Synopsis

# Documentation

newtype MoriarT (m :: Type -> Type) (x :: Type) Source #

The constraint-solving monad transformer. We implement the current computation context with MonadReader, and the current "no goods" list with MonadState.

This transformer exposes its internals through the MonadReader, MonadState, MonadLogic, and MonadIO interfaces, and should therefore not be used directly. The reason is simply that misuse of any of these will break the computation, so the library provides Control.Monad.Holmes and Control.Monad.Watson, who do their best to thwart MoriarT.

Constructors

 MoriarT FieldsunMoriarT :: ReaderT Rule (LogicT (StateT Group m)) x
Instances

runAll :: Monad m => MoriarT m x -> m [x] Source #

Run a MoriarT computation and return the list of all valid branches' results, in the order in which they were discovered.

runOne :: Monad m => MoriarT m x -> m (Maybe x) Source #

Run a MoriarT computation and return the first valid branch's result.

solve :: (PrimMonad m, EqR f, Merge (f x), Typeable x) => Config (MoriarT m) (f x) -> (forall m'. MonadCell m' => [Prop m' (f x)] -> Prop m' (f Bool)) -> MoriarT m [f x] Source #

Given an input configuration, and a predicate on those input variables, compute the configurations that satisfy the predicate. This result (or these results) can be extracted using runOne or runAll.

unsafeRead :: PrimMonad m => Cell (MoriarT m) x -> MoriarT m x Source #

Unsafely read from a cell. This operation is unsafe because it doesn't factor this cell into the provenance of any subsequent writes. If this value ends up causing a contradiction, we may end up removing branches of the search tree that are totally valid! This operation is safe as long as it is the very last thing you do in a computation, and its value is never used to influence any writes in any way.