Control.Monad.MoriarT

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).

Documentation

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

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

MonadTrans MoriarT

Defined in Control.Monad.MoriarT

Methods

lift :: Monad m => m a -> MoriarT m a

Monad (MoriarT m)

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)

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)

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)

Defined in Control.Monad.MoriarT

Methods

liftIO :: IO a -> MoriarT m a

Alternative (MoriarT m)

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)

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)

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)

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)

Defined in Control.Monad.MoriarT

Associated Types

data Cell (MoriarT m) :: Type -> Type

Methods

discard :: MoriarT m x

fill :: x -> MoriarT m (Cell (MoriarT m) x)

watch :: Cell (MoriarT m) x -> (x -> MoriarT m ()) -> MoriarT m ()

with :: Cell (MoriarT m) x -> (x -> MoriarT m ()) -> MoriarT m ()

write :: Merge x => Cell (MoriarT m) x -> x -> MoriarT m ()

Semigroup x => Semigroup (MoriarT m x)

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)

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)

Defined in Control.Monad.MoriarT

type PrimState (MoriarT m) = PrimState m

newtype Cell (MoriarT m) content

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]

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)

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]

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

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.