| logict-0.2.1: A backtracking logic-programming monad. | Contents | Index |
|
Control.Monad.Logic.Class | Portability | non-portable (multi-parameter type classes) | Stability | experimental | Maintainer | dan.doel@gmail.com |
|
|
|
|
|
Description |
A backtracking, logic programming monad.
Adapted from the paper
Backtracking, Interleaving, and Terminating
Monad Transformers, by
Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, Amr Sabry
(http://www.cs.rutgers.edu/~ccshan/logicprog/LogicT-icfp2005.pdf)
|
|
Synopsis |
|
|
|
Documentation |
|
class MonadPlus m => MonadLogic m where |
Minimal implementation: msplit
| | Methods | msplit :: m a -> m (Maybe (a, m a)) | Attempts to split the computation, giving access to the first
result. Satisfies the following laws:
msplit mzero == return Nothing
msplit (return a `mplus` m) == return (Just (a, m))
| | interleave :: m a -> m a -> m a | Fair disjunction. It is possible for a logical computation
to have an infinite number of potential results, for instance:
odds = return 1 `mplus` liftM (2+) odds
Such computations can cause problems in some circumstances. Consider:
do x <- odds `mplus` return 2
if even x then return x else mzero
Such a computation may never consider the 'return 2', and will
therefore never terminate. By contrast, interleave ensures fair
consideration of both branches of a disjunction
| | (>>-) :: m a -> (a -> m b) -> m b | Fair conjunction. Similarly to the previous function, consider
the distributivity law for MonadPlus:
(mplus a b) >>= k = (a >>= k) `mplus` (b >>= k)
If 'a >>= k' can backtrack arbitrarily many tmes, (b >>= k) may never
be considered. (>>-) takes similar care to consider both branches of
a disjunctive computation.
| | ifte :: m a -> (a -> m b) -> m b -> m b | Logical conditional. The equivalent of Prolog's soft-cut. If its
first argument succeeds at all, then the results will be fed into
the success branch. Otherwise, the failure branch is taken.
satisfies the following laws:
ifte (return a) th el == th a
ifte mzero th el == el
ifte (return a `mplus` m) th el == th a `mplus` (m >>= th)
| | once :: m a -> m a | Pruning. Selects one result out of many. Useful for when multiple
results of a computation will be equivalent, or should be treated as
such.
|
| | Instances | |
|
|
reflect :: MonadLogic m => Maybe (a, m a) -> m a |
The inverse of msplit. Satisfies the following law:
msplit m >>= reflect == m
|
|
Produced by Haddock version 0.8 |