h$2{0*      !"#$%&'()(c) 2007-2014 Dan Doel, (c) 2011-2013 Edward Kmett, (c) 2014 Roman Cheplyaka, (c) 2020-2021 Andrew Lelechenko, (c) 2020-2021 Kevin QuickBSD3/Andrew Lelechenko Safe%| logict(A backtracking, logic programming monad.logict Attempts to split the computation, giving access to the first result. Satisfies the following laws: msplit empty == pure Nothing msplit (pure a <|> m) == pure (Just (a, m))logictFair disjunction. It is possible for a logical computation to have an infinite number of potential results, for instance: !odds = pure 1 <|> fmap (+ 2) oddsSuch computations can cause problems in some circumstances. Consider: two = do x <- odds <|> pure 2 if even x then pure x else empty observe two...never completes...&Such a computation may never consider * 2, and therefore even  two9 will never return any results. By contrast, using  in place of + ensures fair consideration of both branches of a disjunction. fairTwo = do x <- odds `interleave` pure 2 if even x then pure x else emptyobserve fairTwo2Note that even with  this computation will never terminate after returning 2: only the first value can be safely observed, after which each odd value becomes , (equivalent to  http://lpn.swi-prolog.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse45 Prolog's fail) which does not stop the evaluation but indicates there is no value to return yet.Unlike +,  is not associative:2let x = [1,2,3]; y = [4,5,6]; z = [7,8,9] :: [Int]x `interleave` y [1,4,2,5,3,6]!(x `interleave` y) `interleave` z[1,7,4,8,2,9,5,3,6]y `interleave` z [4,7,5,8,6,9]!x `interleave` (y `interleave` z)[1,4,2,7,3,5,8,6,9]logictFair conjunction. Similarly to the previous function, consider the distributivity law, naturally expected from -: )(a <|> b) >>= k = (a >>= k) <|> (b >>= k)If a . k' can backtrack arbitrarily many times, b . k may never be considered. In logic statements, "backtracking" is the process of discarding the current possible solution value and returning to a previous decision point where a new value can be obtained and tried. For example:do { x <- pure 0 <|> pure 1 <|> pure 2; if even x then pure x else empty } :: [Int][0,2] Here, the x- value can be produced three times, where + represents the decision points of that production. The subsequent if statement specifies , (fail) if x: is odd, causing it to be discarded and a return to an + decision point to get the next x.The statement "a . k can backtrack arbitrarily many times" means that the computation is resulting in , and that a has an infinite number of + applications to return to. This is called a conjunctive computation because the logic for a and k must both succeed (i.e. * a value instead of ,).Similar to the way ; allows both branches of a disjunctive computation, the  operator takes care to consider both branches of a conjunctive computation.Consider the operation: odds = pure 1 <|> fmap (2 +) odds oddsPlus n = odds >>= \a -> pure (a + n) g = do x <- (pure 0 <|> pure 1) >>= oddsPlus if even x then pure x else emptyobserveMany 3 g...never completes...This will never produce any value because all values produced by the do program come from the * 1 driven operation (adding one to the sequence of odd values, resulting in the even values that are allowed by the test in the second line), but the * 0 input to oddsPlus$ generates an infinite number of ,1 failures so the even values generated by the * 1' alternative are never seen. Using  here instead of +? does not help due to the aforementioned distributivity law.Also note that the do notation desugars to .6 bind operations, so the following would also fail: do a <- pure 0 <|> pure 1 x <- oddsPlus a if even x then pure x else emptyThe solution is to use the 2 in place of the normal monadic bind operation . when fairness between alternative productions is needed in a conjunction of statements (rules): h = do x <- (pure 0 <|> pure 1) >>- oddsPlus if even x then pure x else emptyobserveMany 3 h[2,4,6],However, a bit of care is needed when using  because, unlike .&, it is not associative. For example:let m = [2,7] :: [Int]let k x = [x, x + 1]let h x = [x, x * 2]m >>= (\x -> k x >>= h)[2,4,3,6,7,14,8,16] (m >>= k) >>= h -- same as above[2,4,3,6,7,14,8,16]m >>- (\x -> k x >>- h)[2,7,3,8,4,14,6,16]1(m >>- k) >>- h -- central elements are different[2,7,4,3,14,8,6,16]1This means that the following will be productive: (pure 0 <|> pure 1) >>- oddsPlus >>- \x -> if even x then pure x else emptyWhich is equivalent to ((pure 0 <|> pure 1) >>- oddsPlus) >>- (\x -> if even x then pure x else empty)But the following will not be productive: (pure 0 <|> pure 1) >>- (\a -> (oddsPlus a >>- \x -> if even x then pure x else empty));Since do notation desugaring results in the latter, the RebindableSyntax language pragma cannot easily be used either. Instead, it is recommended to carefully use explicit  only when needed.logictPruning. Selects one result out of many. Useful for when multiple results of a computation will be equivalent, or should be treated as such.;As an example, here's a way to determine if a number is  +https://wikipedia.org/wiki/Composite_number composite (has non-trivial integer divisors, i.e. not a prime number): choose = foldr ((<|>) . pure) empty divisors n = do a <- choose [2..n-1] b <- choose [2..n-1] guard (a * b == n) pure (a, b) composite_ v = do _ <- divisors v pure "Composite"=While this works as intended, it actually does too much work:observeAll (composite_ 20)4["Composite", "Composite", "Composite", "Composite"]Because there are multiple divisors of 20, and they can also occur in either order:observeAll (divisors 20)[(2,10), (4,5), (5,4), (10,2)]Clearly one could just use ? here to get the first non-prime result, but if the call to  composite2 is in the middle of other logic code then use  instead. composite v = do _ <- once (divisors v) pure "Composite"observeAll (composite 20) ["Composite"]logictInverts a logic computation. If m& succeeds with at least one value,  m fails. If m fails, then  m succeeds with the value ().For example, evaluating if a number is prime can be based on the failure to find divisors of a number: choose = foldr ((<|>) . pure) empty divisors n = do d <- choose [2..n-1] guard (n `rem` d == 0) pure d prime v = do _ <- lnot (divisors v) pure TrueobserveAll (prime 20)[]observeAll (prime 19)[True]Here if divisors never succeeds, then the : will succeed and the number will be declared as prime.logictLogical  conditional. The equivalent of  http://lpn.swi-prolog.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse44Prolog'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. The failure branch is never considered if the first argument has any successes. The ' function satisfies the following laws: ifte (pure a) th el == th a ifte empty th el == el ifte (pure a <|> m) th el == th a <|> (m >>= th)For example, the previous prime function returned nothing if the number was not prime, but if it should return /' instead, the following can be used: choose = foldr ((<|>) . pure) empty divisors n = do d <- choose [2..n-1] guard (n `rem` d == 0) pure d prime v = once (ifte (divisors v) (const (pure True)) (pure False))observeAll (prime 20)[False]observeAll (prime 19)[True].Notice that this cannot be done with a simple  if-then-else because divisors either generates values or it does not, so there's no "false" condition to check with a simple if statement.logictThe inverse of . Satisfies the following law: msplit m >>= reflect == mlogictSee note on splitting above. logictSee note on splitting above. logictNote that splitting a transformer does not allow you to provide different input to the monadic object returned. For instance, in: let Just (_, rm') = runReaderT (msplit rm) r in runReaderT rm' r'r' will be ignored, because r/ was already threaded through the computation.1(c) 2007-2014 Dan Doel, (c) 2011-2013 Edward Kmett, (c) 2014 Roman Cheplyaka, (c) 2020-2021 Andrew Lelechenko, (c) 2020-2021 Kevin QuickBSD3/Andrew Lelechenko Safe>0G logict The basic   monad, for performing backtracking computations returning values (e.g.   a will return values of type a). logictA monad transformer for performing backtracking computations layered over another monad m.logict!Extracts the first result from a  6 computation, failing if there are no results at all.logictExtracts all results from a  6 computation, unless blocked by the underlying monad.For example, given%let nats = pure 0 <|> fmap (+ 1) natssome monads (like 0, , , and  ) will be productive:'take 5 $ runIdentity (observeAllT nats) [0,1,2,3,4]but others (like   , and    ) will not:(take 20 <$> runExcept (observeAllT nats)?In general, if the underlying monad manages control flow then 4 may be unproductive under infinite branching, and  should be used instead.logict0Extracts up to a given number of results from a   computation.logictRuns a   computation with the specified initial success and failure continuations.The second argument ("success continuation") takes one result of the  > computation and the monad to run for any subsequent matches.The third argument ("failure continuation") is called when the  ! cannot produce any more results. For example:'yieldWords = foldr ((<|>) . pure) empty&showEach wrd nxt = putStrLn wrd >> nxtrunLogicT (yieldWords ["foo", "bar"]) showEach (putStrLn "none!")foobarnone!5runLogicT (yieldWords []) showEach (putStrLn "none!")none!showFirst wrd _ = putStrLn wrdrunLogicT (yieldWords ["foo", "bar"]) showFirst (putStrLn "none!")foologictA smart constructor for   computations.logict!Extracts the first result from a  / computation, failing if there are no results.%observe (pure 5 <|> pure 3 <|> empty)5 observe empty*** Exception: No answer.logictExtracts all results from a   computation.9observe (pure 5 <|> empty <|> empty <|> pure 3 <|> empty)[5,3]logict0Extracts up to a given number of results from a   computation.%let nats = pure 0 <|> fmap (+ 1) natsobserveMany 5 nats [0,1,2,3,4]logictRuns a   computation with the specified initial success and failure continuations.runLogic empty (+) 00,runLogic (pure 5 <|> pure 3 <|> empty) (+) 081234.56789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ-[\]^    !"#$%&'()*+,-./01234567867967:67;67<=>?6@A6BC67D67E67F67G67H67I67J6KL6KM6NO6NP6QR6QS6BT6BU6BV6BW6BX6BY6BZ6B[6B\6B]6B^6B_6B`6Ba6Nb6cd6ce6cf6cg6hi67j67k67l67m67n67o67p67q67r67stuvtuw%logict-0.7.1.0-K10abzowQPaIJcN4T5cL97Control.Monad.Logic.ClassControl.Monad.LogicobserveControl.Monad.ReaderReaderControl.Monad.WriterWriterControl.Monad.StateStateControl.Monad.ExceptExceptTControl.Monad.ContContT MonadLogicmsplit interleave>>-oncelnotiftereflect$fMonadLogicStateT$fMonadLogicStateT0$fMonadLogicReaderT$fMonadLogic[]LogicLogicTunLogicTobserveT observeAllT observeManyT runLogicTlogic observeAll observeManyrunLogic$fMonadErroreLogicT$fMonadStatesLogicT$fMonadReaderrLogicT$fTraversableLogicT$fFoldableLogicT$fFoldableLogicT0$fMonadLogicLogicT$fMonadIOLogicT$fMonadTransLogicT$fMonoidLogicT$fSemigroupLogicT$fMonadPlusLogicT$fMonadFailLogicT $fMonadLogicT$fAlternativeLogicT$fApplicativeLogicT$fFunctorLogicTbaseGHC.Basepure<|>empty MonadPlus>>=ghc-prim GHC.TypesFalseData.Functor.IdentityIdentity Control.MonadguardjoinMonad>>returnFunctorfmap<$Control.Monad.Fail MonadFailfailData.TraversablemapMsequenceControl.Monad.IO.ClassMonadIOliftIOmfilter<$!>unless replicateM_ replicateMfoldM_foldM zipWithM_zipWithM mapAndUnzipMforever<=<>=>filterMforM Data.Foldablemsum sequence_forM_mapM_ Data.FunctorvoidapliftM5liftM4liftM3liftM2liftMwhen=<<mzeromplustransformers-0.5.6.2Control.Monad.Trans.Class MonadTranslift