Control.Monad.Logic

Adapted from the paper Backtracking, Interleaving, and Terminating Monad Transformers by Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, Amr Sabry. Note that the paper uses MonadPlus vocabulary (mzero and mplus), while examples below prefer empty and <|> from Alternative.

Documentation

module Control.Monad.Logic.Class

The Logic monad

type Logic = LogicT Identity

The basic Logic monad, for performing backtracking computations returning values (e.g. Logic a will return values of type a).

logic :: (forall r. (a -> r -> r) -> r -> r) -> Logic a

A smart constructor for Logic computations.

runLogic :: Logic a -> (a -> r -> r) -> r -> r

Runs a Logic computation with the specified initial success and failure continuations.

>>> runLogic empty (+) 0
0

>>> runLogic (pure 5 <|> pure 3 <|> empty) (+) 0
8

observe :: Logic a -> a

Extracts the first result from a Logic computation, failing if there are no results.

>>> observe (pure 5 <|> pure 3 <|> empty)
5

>>> observe empty
*** Exception: No answer.

observeMany :: Int -> Logic a -> [a]

Extracts up to a given number of results from a Logic computation.

>>> let nats = pure 0 <|> fmap (+ 1) nats
>>> observeMany 5 nats
[0,1,2,3,4]

observeAll :: Logic a -> [a]

Extracts all results from a Logic computation.

>>> observe (pure 5 <|> empty <|> empty <|> pure 3 <|> empty)
[5,3]

The LogicT monad transformer

newtype LogicT m a

A monad transformer for performing backtracking computations layered over another monad m.

Constructors

LogicT

Fields

• unLogicT :: forall r. (a -> m r -> m r) -> m r -> m r

Instances

MonadTrans LogicT

Defined in Control.Monad.Logic

Methods

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

MonadState s m => MonadState s (LogicT m)

Defined in Control.Monad.Logic

Methods

get :: LogicT m s

put :: s -> LogicT m ()

state :: (s -> (a, s)) -> LogicT m a

MonadReader r m => MonadReader r (LogicT m)

Defined in Control.Monad.Logic

Methods

ask :: LogicT m r

local :: (r -> r) -> LogicT m a -> LogicT m a

reader :: (r -> a) -> LogicT m a

MonadError e m => MonadError e (LogicT m)

Defined in Control.Monad.Logic

Methods

throwError :: e -> LogicT m a

catchError :: LogicT m a -> (e -> LogicT m a) -> LogicT m a

Monad (LogicT m)

Defined in Control.Monad.Logic

Methods

(>>=) :: LogicT m a -> (a -> LogicT m b) -> LogicT m b

(>>) :: LogicT m a -> LogicT m b -> LogicT m b

return :: a -> LogicT m a

Functor (LogicT f)

Defined in Control.Monad.Logic

Methods

fmap :: (a -> b) -> LogicT f a -> LogicT f b

(<$) :: a -> LogicT f b -> LogicT f a

MonadFail (LogicT m)

Defined in Control.Monad.Logic

Methods

fail :: String -> LogicT m a

Applicative (LogicT f)

Defined in Control.Monad.Logic

Methods

pure :: a -> LogicT f a

(<*>) :: LogicT f (a -> b) -> LogicT f a -> LogicT f b

liftA2 :: (a -> b -> c) -> LogicT f a -> LogicT f b -> LogicT f c

(*>) :: LogicT f a -> LogicT f b -> LogicT f b

(<*) :: LogicT f a -> LogicT f b -> LogicT f a

(Applicative m, Foldable m) => Foldable (LogicT m)

Defined in Control.Monad.Logic

Methods

fold :: Monoid m0 => LogicT m m0 -> m0

foldMap :: Monoid m0 => (a -> m0) -> LogicT m a -> m0

foldMap' :: Monoid m0 => (a -> m0) -> LogicT m a -> m0

foldr :: (a -> b -> b) -> b -> LogicT m a -> b

foldr' :: (a -> b -> b) -> b -> LogicT m a -> b

foldl :: (b -> a -> b) -> b -> LogicT m a -> b

foldl' :: (b -> a -> b) -> b -> LogicT m a -> b

foldr1 :: (a -> a -> a) -> LogicT m a -> a

foldl1 :: (a -> a -> a) -> LogicT m a -> a

toList :: LogicT m a -> [a]

null :: LogicT m a -> Bool

length :: LogicT m a -> Int

elem :: Eq a => a -> LogicT m a -> Bool

maximum :: Ord a => LogicT m a -> a

minimum :: Ord a => LogicT m a -> a

sum :: Num a => LogicT m a -> a

product :: Num a => LogicT m a -> a

Foldable (LogicT Identity)

Defined in Control.Monad.Logic

Methods

fold :: Monoid m => LogicT Identity m -> m

foldMap :: Monoid m => (a -> m) -> LogicT Identity a -> m

foldMap' :: Monoid m => (a -> m) -> LogicT Identity a -> m

foldr :: (a -> b -> b) -> b -> LogicT Identity a -> b

foldr' :: (a -> b -> b) -> b -> LogicT Identity a -> b

foldl :: (b -> a -> b) -> b -> LogicT Identity a -> b

foldl' :: (b -> a -> b) -> b -> LogicT Identity a -> b

foldr1 :: (a -> a -> a) -> LogicT Identity a -> a

foldl1 :: (a -> a -> a) -> LogicT Identity a -> a

toList :: LogicT Identity a -> [a]

null :: LogicT Identity a -> Bool

length :: LogicT Identity a -> Int

elem :: Eq a => a -> LogicT Identity a -> Bool

maximum :: Ord a => LogicT Identity a -> a

minimum :: Ord a => LogicT Identity a -> a

sum :: Num a => LogicT Identity a -> a

product :: Num a => LogicT Identity a -> a

Traversable (LogicT Identity)

Defined in Control.Monad.Logic

Methods

traverse :: Applicative f => (a -> f b) -> LogicT Identity a -> f (LogicT Identity b)

sequenceA :: Applicative f => LogicT Identity (f a) -> f (LogicT Identity a)

mapM :: Monad m => (a -> m b) -> LogicT Identity a -> m (LogicT Identity b)

sequence :: Monad m => LogicT Identity (m a) -> m (LogicT Identity a)

MonadIO m => MonadIO (LogicT m)

Defined in Control.Monad.Logic

Methods

liftIO :: IO a -> LogicT m a

Alternative (LogicT f)

Defined in Control.Monad.Logic

Methods

empty :: LogicT f a

(<|>) :: LogicT f a -> LogicT f a -> LogicT f a

some :: LogicT f a -> LogicT f [a]

many :: LogicT f a -> LogicT f [a]

MonadPlus (LogicT m)

Defined in Control.Monad.Logic

Methods

mzero :: LogicT m a

mplus :: LogicT m a -> LogicT m a -> LogicT m a

Monad m => MonadLogic (LogicT m)

Defined in Control.Monad.Logic

Methods

msplit :: LogicT m a -> LogicT m (Maybe (a, LogicT m a))

interleave :: LogicT m a -> LogicT m a -> LogicT m a

(>>-) :: LogicT m a -> (a -> LogicT m b) -> LogicT m b

once :: LogicT m a -> LogicT m a

lnot :: LogicT m a -> LogicT m ()

ifte :: LogicT m a -> (a -> LogicT m b) -> LogicT m b -> LogicT m b

Semigroup (LogicT m a)

Defined in Control.Monad.Logic

Methods

(<>) :: LogicT m a -> LogicT m a -> LogicT m a

sconcat :: NonEmpty (LogicT m a) -> LogicT m a

stimes :: Integral b => b -> LogicT m a -> LogicT m a

Monoid (LogicT m a)

Defined in Control.Monad.Logic

Methods

mempty :: LogicT m a

mappend :: LogicT m a -> LogicT m a -> LogicT m a

mconcat :: [LogicT m a] -> LogicT m a

runLogicT :: LogicT m a -> (a -> m r -> m r) -> m r -> m r

Runs a LogicT computation with the specified initial success and failure continuations.

The second argument ("success continuation") takes one result of the LogicT computation and the monad to run for any subsequent matches.

The third argument ("failure continuation") is called when the LogicT cannot produce any more results.

For example:

>>> yieldWords = foldr ((<|>) . pure) empty
>>> showEach wrd nxt = putStrLn wrd >> nxt
>>> runLogicT (yieldWords ["foo", "bar"]) showEach (putStrLn "none!")
foo
bar
none!
>>> runLogicT (yieldWords []) showEach (putStrLn "none!")
none!
>>> showFirst wrd _ = putStrLn wrd
>>> runLogicT (yieldWords ["foo", "bar"]) showFirst (putStrLn "none!")
foo

observeT :: MonadFail m => LogicT m a -> m a

Extracts the first result from a LogicT computation, failing if there are no results at all.

observeManyT :: Monad m => Int -> LogicT m a -> m [a]

Extracts up to a given number of results from a LogicT computation.

observeAllT :: Applicative m => LogicT m a -> m [a]

Extracts all results from a LogicT computation, unless blocked by the underlying monad.

For example, given

>>> let nats = pure 0 <|> fmap (+ 1) nats

some monads (like Identity, Reader, Writer, and State) will be productive:

>>> take 5 $ runIdentity (observeAllT nats)
[0,1,2,3,4]

but others (like ExceptT, and ContT) will not:

>>> take 20 <$> runExcept (observeAllT nats)

In general, if the underlying monad manages control flow then observeAllT may be unproductive under infinite branching, and observeManyT should be used instead.

module Control.Monad

module Control.Monad.Trans