 logict0.2.2: A backtracking logicprogramming monad.  Contents  Index 

Control.Monad.Logic.Class  Portability  nonportable (multiparameter 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, Chungchieh Shan, Daniel P. Friedman, Amr Sabry
(http://www.cs.rutgers.edu/~ccshan/logicprog/LogicTicfp2005.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 softcut. 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 