{-# OPTIONS_GHC -Werror -fno-warn-orphans #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE NoMonomorphismRestriction #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE Safe #-}
-- The following is needed to define MonadPlus instance. It is decidable
-- (there is no recursion!), but GHC cannot see that.
{-# LANGUAGE UndecidableInstances #-}
-- | Another implementation of nondeterministic choice effect
module Control.Eff.NdetEff where
import Control.Eff
import Data.OpenUnion
import Control.Monad
import Control.Applicative
-- | A different implementation, more directly mapping to MonadPlus
-- interface
data NdetEff a where
MZero :: NdetEff a
MPlus :: NdetEff Bool
instance Member NdetEff r => Alternative (Eff r) where
empty = mzero
(<|>) = mplus
instance Member NdetEff r => MonadPlus (Eff r) where
mzero = send MZero
mplus m1 m2 = send MPlus >>= \x -> if x then m1 else m2
-- | An interpreter
-- The following is very simple, but leaks a lot of memory
-- The cause probably is mapping every failure to empty
-- It takes then a lot of timne and space to store those empty
makeChoiceA0 :: Alternative f => Eff (NdetEff ': r) a -> Eff r (f a)
makeChoiceA0 = handle_relay (return . pure) $ \m k -> case m of
MZero -> return empty
MPlus -> liftM2 (<|>) (k True) (k False)
-- | A different implementation, more involved but faster and taking
-- much less (100 times) less memory.
-- The benefit of the effect framework is that we can have many
-- interpreters.
makeChoiceA :: Alternative f => Eff (NdetEff ': r) a -> Eff r (f a)
makeChoiceA m = loop [] m
where
loop [] (Val x) = return (pure x)
loop (h:t) (Val x) = loop t h >>= \r -> return (pure x <|> r)
loop jq (E u q) = case decomp u of
Right MZero -> case jq of
[] -> return empty
(h:t) -> loop t h
Right MPlus -> loop (qApp q False : jq) (qApp q True)
Left u0 -> E u0 (single (\x -> loop jq (qApp q x)))
-- ------------------------------------------------------------------------
-- Soft-cut: non-deterministic if-then-else, aka Prolog's *->
-- Declaratively,
-- ifte t th el = (t >>= th) `mplus` ((not t) >> el)
-- However, t is evaluated only once. In other words, ifte t th el
-- is equivalent to t >>= th if t has at least one solution.
-- If t fails, ifte t th el is the same as el.
-- We actually implement LogicT, the non-determinism reflection,
-- of which soft-cut is one instance.
-- See the LogicT paper for an explanation
msplit :: Member NdetEff r => Eff r a -> Eff r (Maybe (a, Eff r a))
msplit = loop []
where
-- single result
loop [] (Val x) = return (Just (x,mzero))
-- definite result and perhaps some others
loop jq (Val x) = return (Just (x, msum jq))
-- not yet definite answer
loop jq (E u q) = case prj u of
Just MZero -> case jq of
-- no futher choices
[] -> return Nothing
-- other choices remain, try them
(j:jqT) -> loop jqT j
Just MPlus -> loop ((qApp q False):jq) (qApp q True)
_ -> E u (single k) where k = qComp q (loop jq)
-- Other committed choice primitives can be implemented in terms of msplit
-- The following implementations are directly from the LogicT paper
ifte :: Member NdetEff r => Eff r a -> (a -> Eff r b) -> Eff r b -> Eff r b
ifte t th el = msplit t >>= check
where check Nothing = el
check (Just (sg1,sg2)) = (th sg1) `mplus` (sg2 >>= th)
once :: Member NdetEff r => Eff r a -> Eff r a
once m = msplit m >>= check
where check Nothing = mzero
check (Just (sg1,_)) = return sg1