Copyright (c) 2007-2014 Dan Doel(c) 2011-2013 Edward Kmett(c) 2014 Roman Cheplyaka(c) 2020-2021 Andrew Lelechenko(c) 2020-2021 Kevin Quick BSD3 Andrew Lelechenko Safe Haskell2010

Description

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.

Synopsis

Documentation

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 Source #

A smart constructor for Logic computations.

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

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 Source #

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] Source #

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] Source #

Extracts all results from a Logic computation.

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


newtype LogicT m a Source #

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

Constructors

 LogicT FieldsunLogicT :: forall r. (a -> m r -> m r) -> m r -> m r

Instances

Instances details
 Source # Instance detailsDefined in Control.Monad.Logic Methodslift :: Monad m => m a -> LogicT m a # MonadState s m => MonadState s (LogicT m) Source # Instance detailsDefined in Control.Monad.Logic Methodsget :: LogicT m s #put :: s -> LogicT m () #state :: (s -> (a, s)) -> LogicT m a # MonadReader r m => MonadReader r (LogicT m) Source # Instance detailsDefined in Control.Monad.Logic Methodsask :: 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) Source # Instance detailsDefined in Control.Monad.Logic MethodsthrowError :: e -> LogicT m a #catchError :: LogicT m a -> (e -> LogicT m a) -> LogicT m a # Monad (LogicT m) Source # Instance detailsDefined 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 # Source # Instance detailsDefined in Control.Monad.Logic Methodsfmap :: (a -> b) -> LogicT f a -> LogicT f b #(<$) :: a -> LogicT f b -> LogicT f a # Source # Instance detailsDefined in Control.Monad.Logic Methodsfail :: String -> LogicT m a # Source # Instance detailsDefined in Control.Monad.Logic Methodspure :: 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) Source # Instance detailsDefined in Control.Monad.Logic Methodsfold :: 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 # Source # Instance detailsDefined in Control.Monad.Logic Methodsfold :: 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 # Source # Instance detailsDefined in Control.Monad.Logic Methodstraverse :: 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) Source # Instance detailsDefined in Control.Monad.Logic MethodsliftIO :: IO a -> LogicT m a # Source # Instance detailsDefined in Control.Monad.Logic Methodsempty :: 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] # Source # Instance detailsDefined in Control.Monad.Logic Methodsmzero :: LogicT m a #mplus :: LogicT m a -> LogicT m a -> LogicT m a # Monad m => MonadLogic (LogicT m) Source # Instance detailsDefined in Control.Monad.Logic Methodsmsplit :: LogicT m a -> LogicT m (Maybe (a, LogicT m a)) Source #interleave :: LogicT m a -> LogicT m a -> LogicT m a Source #(>>-) :: LogicT m a -> (a -> LogicT m b) -> LogicT m b Source #once :: LogicT m a -> LogicT m a Source #lnot :: LogicT m a -> LogicT m () Source #ifte :: LogicT m a -> (a -> LogicT m b) -> LogicT m b -> LogicT m b Source # Semigroup (LogicT m a) Source # Instance detailsDefined 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) Source # Instance detailsDefined in Control.Monad.Logic Methodsmempty :: 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 Source # 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 Source # 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] Source # Extracts up to a given number of results from a LogicT computation. observeAllT :: Applicative m => LogicT m a -> m [a] Source # 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.