Copyright	(c) Tom Harding 2020
License	MIT
Safe Haskell	None
Language	Haskell2010

Control.Monad.MoriarT

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

newtype MoriarT (m :: Type -> Type) (x :: Type) = MoriarT {
- unMoriarT :: ReaderT Rule (LogicT (StateT Group m)) x
}
runAll :: Monad m => MoriarT m x -> m [x]
runOne :: Monad m => MoriarT m x -> m (Maybe x)
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]
unsafeRead :: PrimMonad m => Cell (MoriarT m) x -> MoriarT m x

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
Fields unMoriarT :: ReaderT Rule (LogicT (StateT Group m)) x

Instances

Instances details

MonadTrans MoriarT Source #
Instance details Defined in Control.Monad.MoriarT Methods lift :: Monad m => m a -> MoriarT m a #
Monad (MoriarT m) Source #
Instance details Defined in Control.Monad.MoriarT Methods (>>=) :: MoriarT m a -> (a -> MoriarT m b) -> MoriarT m b # (>>) :: MoriarT m a -> MoriarT m b -> MoriarT m b # return :: a -> MoriarT m a #
Functor (MoriarT m) Source #
Instance details Defined in Control.Monad.MoriarT Methods fmap :: (a -> b) -> MoriarT m a -> MoriarT m b # (<$) :: a -> MoriarT m b -> MoriarT m a #
Applicative (MoriarT m) Source #
Instance details Defined in Control.Monad.MoriarT Methods pure :: a -> MoriarT m a # (<>) :: MoriarT m (a -> b) -> MoriarT m a -> MoriarT m b # liftA2 :: (a -> b -> c) -> MoriarT m a -> MoriarT m b -> MoriarT m c # (>) :: MoriarT m a -> MoriarT m b -> MoriarT m b # (<*) :: MoriarT m a -> MoriarT m b -> MoriarT m a #
MonadIO m => MonadIO (MoriarT m) Source #
Instance details Defined in Control.Monad.MoriarT Methods liftIO :: IO a -> MoriarT m a #
Alternative (MoriarT m) Source #
Instance details Defined in Control.Monad.MoriarT Methods empty :: MoriarT m a # (<\|>) :: MoriarT m a -> MoriarT m a -> MoriarT m a # some :: MoriarT m a -> MoriarT m [a] # many :: MoriarT m a -> MoriarT m [a] #
MonadPlus (MoriarT m) Source #
Instance details Defined in Control.Monad.MoriarT Methods mzero :: MoriarT m a # mplus :: MoriarT m a -> MoriarT m a -> MoriarT m a #
Monad m => MonadLogic (MoriarT m) Source #
Instance details Defined in Control.Monad.MoriarT Methods msplit :: MoriarT m a -> MoriarT m (Maybe (a, MoriarT m a)) # interleave :: MoriarT m a -> MoriarT m a -> MoriarT m a # (>>-) :: MoriarT m a -> (a -> MoriarT m b) -> MoriarT m b # ifte :: MoriarT m a -> (a -> MoriarT m b) -> MoriarT m b -> MoriarT m b # once :: MoriarT m a -> MoriarT m a # lnot :: MoriarT m a -> MoriarT m () #
PrimMonad m => PrimMonad (MoriarT m) Source #
Instance details Defined in Control.Monad.MoriarT Associated Types type PrimState (MoriarT m) # Methods primitive :: (State# (PrimState (MoriarT m)) -> (# State# (PrimState (MoriarT m)), a #)) -> MoriarT m a #
PrimMonad m => MonadCell (MoriarT m) Source #
Instance details Defined in Control.Monad.MoriarT Associated Types data Cell (MoriarT m) :: Type -> Type Source # Methods discard :: MoriarT m x Source # fill :: x -> MoriarT m (Cell (MoriarT m) x) Source # watch :: Cell (MoriarT m) x -> (x -> MoriarT m ()) -> MoriarT m () Source # with :: Cell (MoriarT m) x -> (x -> MoriarT m ()) -> MoriarT m () Source # write :: Merge x => Cell (MoriarT m) x -> x -> MoriarT m () Source #
Semigroup x => Semigroup (MoriarT m x) Source #
Instance details Defined in Control.Monad.MoriarT Methods (<>) :: MoriarT m x -> MoriarT m x -> MoriarT m x # sconcat :: NonEmpty (MoriarT m x) -> MoriarT m x # stimes :: Integral b => b -> MoriarT m x -> MoriarT m x #
Monoid x => Monoid (MoriarT m x) Source #
Instance details Defined in Control.Monad.MoriarT Methods mempty :: MoriarT m x # mappend :: MoriarT m x -> MoriarT m x -> MoriarT m x # mconcat :: [MoriarT m x] -> MoriarT m x #
type PrimState (MoriarT m) Source #
Instance details Defined in Control.Monad.MoriarT type PrimState (MoriarT m) = PrimState m
newtype Cell (MoriarT m) content Source #
Instance details Defined in Control.Monad.MoriarT newtype Cell (MoriarT m) content = Cell (MutVar (PrimState m) (Rule, content, MoriarT m ()))

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.