logict-0.7.1.0: A backtracking logic-programming monad.

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
License | BSD3
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell | Safe
Language | Haskell2010

Control.Monad.Logic

Contents

- The Logic monad
- The LogicT monad transformer

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

- module Control.Monad.Logic.Class
- type Logic = LogicT Identity
- logic :: (forall r. (a -> r -> r) -> r -> r) -> Logic a
- runLogic :: Logic a -> (a -> r -> r) -> r -> r
- observe :: Logic a -> a
- observeMany :: Int -> Logic a -> [a]
- observeAll :: Logic a -> [a]
- newtype LogicT m a = LogicT {
  - unLogicT :: forall r. (a -> m r -> m r) -> m r -> m r
  }
- runLogicT :: LogicT m a -> (a -> m r -> m r) -> m r -> m r
- observeT :: MonadFail m => LogicT m a -> m a
- observeManyT :: Monad m => Int -> LogicT m a -> m [a]
- observeAllT :: Applicative m => LogicT m a -> m [a]
- module Control.Monad
- module Control.Monad.Trans

# 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

Instances details

MonadTrans LogicT # |
Instance details Defined in Control.Monad.Logic Methods lift :: Monad m => m a -> LogicT m a #
MonadState s m => MonadState s (LogicT m) # |
Instance details 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) # |
Instance details 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) # |
Instance details 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) # |
Instance details 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) # |
Instance details 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) # |
Instance details Defined in Control.Monad.Logic Methods fail :: String -> LogicT m a #
Applicative (LogicT f) # |
Instance details 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) # |
Instance details 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) # |
Instance details 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) # |
Instance details 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) # |
Instance details Defined in Control.Monad.Logic Methods liftIO :: IO a -> LogicT m a #
Alternative (LogicT f) # |
Instance details 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) # |
Instance details 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) # |
Instance details 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) # |
Instance details 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) # |
Instance details 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