{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE UndecidableInstances #-}

-- | A carrier for 'Cull' and 'NonDet' effects used in tandem (@Cull :+: NonDet@).
--
-- @since 1.0.0.0
module Control.Carrier.Cull.Church
( -- * Cull carrier
  runCull
, runCullA
, runCullM
, CullC(CullC)
  -- * Cull effect
, module Control.Effect.Cull
  -- * NonDet effects
, module Control.Effect.NonDet
) where

import Control.Algebra
import Control.Applicative (liftA2)
import Control.Carrier.NonDet.Church
import Control.Carrier.Reader
import Control.Effect.Cull
import Control.Effect.NonDet
import Control.Monad.Fail as Fail
import Control.Monad.Fix
import Control.Monad.IO.Class
import Control.Monad.Trans.Class

-- | Run a 'Cull' effect with continuations respectively interpreting '<|>', 'pure', and 'empty'. Branches outside of any 'cull' block will not be pruned.
--
-- @
-- runCull fork leaf nil ('pure' a '<|>' 'empty') = leaf a \`fork\` nil
-- @
-- @
-- runCull fork leaf nil ('cull' ('pure' a '<|>' b)) = leaf a
-- @
--
-- @since 1.0.0.0
runCull :: (m b -> m b -> m b) -> (a -> m b) -> m b -> CullC m a -> m b
runCull :: (m b -> m b -> m b) -> (a -> m b) -> m b -> CullC m a -> m b
runCull m b -> m b -> m b
fork a -> m b
leaf m b
nil (CullC ReaderC Bool (NonDetC m) a
m) = (m b -> m b -> m b) -> (a -> m b) -> m b -> NonDetC m a -> m b
forall (m :: * -> *) b a.
(m b -> m b -> m b) -> (a -> m b) -> m b -> NonDetC m a -> m b
runNonDet m b -> m b -> m b
fork a -> m b
leaf m b
nil (Bool -> ReaderC Bool (NonDetC m) a -> NonDetC m a
forall r (m :: * -> *) a. r -> ReaderC r m a -> m a
runReader Bool
False ReaderC Bool (NonDetC m) a
m)
{-# INLINE runCull #-}

-- | Run a 'Cull' effect, interpreting the result into an 'Alternative' functor. Choice is handled with '<|>', embedding with 'pure', and failure with 'empty'.
--
-- @since 1.0.0.0
runCullA :: (Alternative f, Applicative m) => CullC m a -> m (f a)
runCullA :: CullC m a -> m (f a)
runCullA = (m (f a) -> m (f a) -> m (f a))
-> (a -> m (f a)) -> m (f a) -> CullC m a -> m (f a)
forall (m :: * -> *) b a.
(m b -> m b -> m b) -> (a -> m b) -> m b -> CullC m a -> m b
runCull ((f a -> f a -> f a) -> m (f a) -> m (f a) -> m (f a)
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 f a -> f a -> f a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
(<|>)) (f a -> m (f a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (f a -> m (f a)) -> (a -> f a) -> a -> m (f a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure) (f a -> m (f a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure f a
forall (f :: * -> *) a. Alternative f => f a
empty)
{-# INLINE runCullA #-}

-- | Run a 'Cull' effect, mapping results into a 'Monoid'.
--
-- @since 1.0.0.0
runCullM :: (Applicative m, Monoid b) => (a -> b) -> CullC m a -> m b
runCullM :: (a -> b) -> CullC m a -> m b
runCullM a -> b
leaf = (m b -> m b -> m b) -> (a -> m b) -> m b -> CullC m a -> m b
forall (m :: * -> *) b a.
(m b -> m b -> m b) -> (a -> m b) -> m b -> CullC m a -> m b
runCull ((b -> b -> b) -> m b -> m b -> m b
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 b -> b -> b
forall a. Monoid a => a -> a -> a
mappend) (b -> m b
forall (f :: * -> *) a. Applicative f => a -> f a
pure (b -> m b) -> (a -> b) -> a -> m b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
leaf) (b -> m b
forall (f :: * -> *) a. Applicative f => a -> f a
pure b
forall a. Monoid a => a
mempty)
{-# INLINE runCullM #-}

-- | @since 1.0.0.0
newtype CullC m a = CullC { CullC m a -> ReaderC Bool (NonDetC m) a
runCullC :: ReaderC Bool (NonDetC m) a }
  deriving (Functor (CullC m)
a -> CullC m a
Functor (CullC m)
-> (forall a. a -> CullC m a)
-> (forall a b. CullC m (a -> b) -> CullC m a -> CullC m b)
-> (forall a b c.
    (a -> b -> c) -> CullC m a -> CullC m b -> CullC m c)
-> (forall a b. CullC m a -> CullC m b -> CullC m b)
-> (forall a b. CullC m a -> CullC m b -> CullC m a)
-> Applicative (CullC m)
CullC m a -> CullC m b -> CullC m b
CullC m a -> CullC m b -> CullC m a
CullC m (a -> b) -> CullC m a -> CullC m b
(a -> b -> c) -> CullC m a -> CullC m b -> CullC m c
forall a. a -> CullC m a
forall a b. CullC m a -> CullC m b -> CullC m a
forall a b. CullC m a -> CullC m b -> CullC m b
forall a b. CullC m (a -> b) -> CullC m a -> CullC m b
forall a b c. (a -> b -> c) -> CullC m a -> CullC m b -> CullC m c
forall (m :: * -> *). Functor (CullC m)
forall (f :: * -> *).
Functor f
-> (forall a. a -> f a)
-> (forall a b. f (a -> b) -> f a -> f b)
-> (forall a b c. (a -> b -> c) -> f a -> f b -> f c)
-> (forall a b. f a -> f b -> f b)
-> (forall a b. f a -> f b -> f a)
-> Applicative f
forall (m :: * -> *) a. a -> CullC m a
forall (m :: * -> *) a b. CullC m a -> CullC m b -> CullC m a
forall (m :: * -> *) a b. CullC m a -> CullC m b -> CullC m b
forall (m :: * -> *) a b.
CullC m (a -> b) -> CullC m a -> CullC m b
forall (m :: * -> *) a b c.
(a -> b -> c) -> CullC m a -> CullC m b -> CullC m c
<* :: CullC m a -> CullC m b -> CullC m a
$c<* :: forall (m :: * -> *) a b. CullC m a -> CullC m b -> CullC m a
*> :: CullC m a -> CullC m b -> CullC m b
$c*> :: forall (m :: * -> *) a b. CullC m a -> CullC m b -> CullC m b
liftA2 :: (a -> b -> c) -> CullC m a -> CullC m b -> CullC m c
$cliftA2 :: forall (m :: * -> *) a b c.
(a -> b -> c) -> CullC m a -> CullC m b -> CullC m c
<*> :: CullC m (a -> b) -> CullC m a -> CullC m b
$c<*> :: forall (m :: * -> *) a b.
CullC m (a -> b) -> CullC m a -> CullC m b
pure :: a -> CullC m a
$cpure :: forall (m :: * -> *) a. a -> CullC m a
$cp1Applicative :: forall (m :: * -> *). Functor (CullC m)
Applicative, a -> CullC m b -> CullC m a
(a -> b) -> CullC m a -> CullC m b
(forall a b. (a -> b) -> CullC m a -> CullC m b)
-> (forall a b. a -> CullC m b -> CullC m a) -> Functor (CullC m)
forall a b. a -> CullC m b -> CullC m a
forall a b. (a -> b) -> CullC m a -> CullC m b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
forall (m :: * -> *) a b. a -> CullC m b -> CullC m a
forall (m :: * -> *) a b. (a -> b) -> CullC m a -> CullC m b
<$ :: a -> CullC m b -> CullC m a
$c<$ :: forall (m :: * -> *) a b. a -> CullC m b -> CullC m a
fmap :: (a -> b) -> CullC m a -> CullC m b
$cfmap :: forall (m :: * -> *) a b. (a -> b) -> CullC m a -> CullC m b
Functor, Applicative (CullC m)
a -> CullC m a
Applicative (CullC m)
-> (forall a b. CullC m a -> (a -> CullC m b) -> CullC m b)
-> (forall a b. CullC m a -> CullC m b -> CullC m b)
-> (forall a. a -> CullC m a)
-> Monad (CullC m)
CullC m a -> (a -> CullC m b) -> CullC m b
CullC m a -> CullC m b -> CullC m b
forall a. a -> CullC m a
forall a b. CullC m a -> CullC m b -> CullC m b
forall a b. CullC m a -> (a -> CullC m b) -> CullC m b
forall (m :: * -> *). Applicative (CullC m)
forall (m :: * -> *).
Applicative m
-> (forall a b. m a -> (a -> m b) -> m b)
-> (forall a b. m a -> m b -> m b)
-> (forall a. a -> m a)
-> Monad m
forall (m :: * -> *) a. a -> CullC m a
forall (m :: * -> *) a b. CullC m a -> CullC m b -> CullC m b
forall (m :: * -> *) a b.
CullC m a -> (a -> CullC m b) -> CullC m b
return :: a -> CullC m a
$creturn :: forall (m :: * -> *) a. a -> CullC m a
>> :: CullC m a -> CullC m b -> CullC m b
$c>> :: forall (m :: * -> *) a b. CullC m a -> CullC m b -> CullC m b
>>= :: CullC m a -> (a -> CullC m b) -> CullC m b
$c>>= :: forall (m :: * -> *) a b.
CullC m a -> (a -> CullC m b) -> CullC m b
$cp1Monad :: forall (m :: * -> *). Applicative (CullC m)
Monad, Monad (CullC m)
Monad (CullC m)
-> (forall a. String -> CullC m a) -> MonadFail (CullC m)
String -> CullC m a
forall a. String -> CullC m a
forall (m :: * -> *).
Monad m -> (forall a. String -> m a) -> MonadFail m
forall (m :: * -> *). MonadFail m => Monad (CullC m)
forall (m :: * -> *) a. MonadFail m => String -> CullC m a
fail :: String -> CullC m a
$cfail :: forall (m :: * -> *) a. MonadFail m => String -> CullC m a
$cp1MonadFail :: forall (m :: * -> *). MonadFail m => Monad (CullC m)
Fail.MonadFail, Monad (CullC m)
Monad (CullC m)
-> (forall a. IO a -> CullC m a) -> MonadIO (CullC m)
IO a -> CullC m a
forall a. IO a -> CullC m a
forall (m :: * -> *).
Monad m -> (forall a. IO a -> m a) -> MonadIO m
forall (m :: * -> *). MonadIO m => Monad (CullC m)
forall (m :: * -> *) a. MonadIO m => IO a -> CullC m a
liftIO :: IO a -> CullC m a
$cliftIO :: forall (m :: * -> *) a. MonadIO m => IO a -> CullC m a
$cp1MonadIO :: forall (m :: * -> *). MonadIO m => Monad (CullC m)
MonadIO)

instance Alternative (CullC m) where
  empty :: CullC m a
empty = ReaderC Bool (NonDetC m) a -> CullC m a
forall (m :: * -> *) a. ReaderC Bool (NonDetC m) a -> CullC m a
CullC ReaderC Bool (NonDetC m) a
forall (f :: * -> *) a. Alternative f => f a
empty
  {-# INLINE empty #-}

  CullC ReaderC Bool (NonDetC m) a
l <|> :: CullC m a -> CullC m a -> CullC m a
<|> CullC ReaderC Bool (NonDetC m) a
r = ReaderC Bool (NonDetC m) a -> CullC m a
forall (m :: * -> *) a. ReaderC Bool (NonDetC m) a -> CullC m a
CullC (ReaderC Bool (NonDetC m) a -> CullC m a)
-> ReaderC Bool (NonDetC m) a -> CullC m a
forall a b. (a -> b) -> a -> b
$ (Bool -> NonDetC m a) -> ReaderC Bool (NonDetC m) a
forall r (m :: * -> *) a. (r -> m a) -> ReaderC r m a
ReaderC ((Bool -> NonDetC m a) -> ReaderC Bool (NonDetC m) a)
-> (Bool -> NonDetC m a) -> ReaderC Bool (NonDetC m) a
forall a b. (a -> b) -> a -> b
$ \ Bool
cull ->
    if Bool
cull then
      (forall b. (m b -> m b -> m b) -> (a -> m b) -> m b -> m b)
-> NonDetC m a
forall (m :: * -> *) a.
(forall b. (m b -> m b -> m b) -> (a -> m b) -> m b -> m b)
-> NonDetC m a
NonDetC ((forall b. (m b -> m b -> m b) -> (a -> m b) -> m b -> m b)
 -> NonDetC m a)
-> (forall b. (m b -> m b -> m b) -> (a -> m b) -> m b -> m b)
-> NonDetC m a
forall a b. (a -> b) -> a -> b
$ \ m b -> m b -> m b
fork a -> m b
leaf m b
nil ->
        (m b -> m b -> m b) -> (a -> m b) -> m b -> NonDetC m a -> m b
forall (m :: * -> *) b a.
(m b -> m b -> m b) -> (a -> m b) -> m b -> NonDetC m a -> m b
runNonDet m b -> m b -> m b
fork a -> m b
leaf ((m b -> m b -> m b) -> (a -> m b) -> m b -> NonDetC m a -> m b
forall (m :: * -> *) b a.
(m b -> m b -> m b) -> (a -> m b) -> m b -> NonDetC m a -> m b
runNonDet m b -> m b -> m b
fork a -> m b
leaf m b
nil (Bool -> ReaderC Bool (NonDetC m) a -> NonDetC m a
forall r (m :: * -> *) a. r -> ReaderC r m a -> m a
runReader Bool
cull ReaderC Bool (NonDetC m) a
r)) (Bool -> ReaderC Bool (NonDetC m) a -> NonDetC m a
forall r (m :: * -> *) a. r -> ReaderC r m a -> m a
runReader Bool
cull ReaderC Bool (NonDetC m) a
l)
    else
      Bool -> ReaderC Bool (NonDetC m) a -> NonDetC m a
forall r (m :: * -> *) a. r -> ReaderC r m a -> m a
runReader Bool
cull ReaderC Bool (NonDetC m) a
l NonDetC m a -> NonDetC m a -> NonDetC m a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> Bool -> ReaderC Bool (NonDetC m) a -> NonDetC m a
forall r (m :: * -> *) a. r -> ReaderC r m a -> m a
runReader Bool
cull ReaderC Bool (NonDetC m) a
r
  {-# INLINE (<|>) #-}

-- | Separate fixpoints are computed for each branch.
deriving instance MonadFix m => MonadFix (CullC m)

instance MonadPlus (CullC m)

instance MonadTrans CullC where
  lift :: m a -> CullC m a
lift = ReaderC Bool (NonDetC m) a -> CullC m a
forall (m :: * -> *) a. ReaderC Bool (NonDetC m) a -> CullC m a
CullC (ReaderC Bool (NonDetC m) a -> CullC m a)
-> (m a -> ReaderC Bool (NonDetC m) a) -> m a -> CullC m a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonDetC m a -> ReaderC Bool (NonDetC m) a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (NonDetC m a -> ReaderC Bool (NonDetC m) a)
-> (m a -> NonDetC m a) -> m a -> ReaderC Bool (NonDetC m) a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. m a -> NonDetC m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift
  {-# INLINE lift #-}

instance Algebra sig m => Algebra (Cull :+: NonDet :+: sig) (CullC m) where
  alg :: Handler ctx n (CullC m)
-> (:+:) Cull (NonDet :+: sig) n a -> ctx () -> CullC m (ctx a)
alg Handler ctx n (CullC m)
hdl (:+:) Cull (NonDet :+: sig) n a
sig ctx ()
ctx = case (:+:) Cull (NonDet :+: sig) n a
sig of
    L (Cull n a
m)       -> ReaderC Bool (NonDetC m) (ctx a) -> CullC m (ctx a)
forall (m :: * -> *) a. ReaderC Bool (NonDetC m) a -> CullC m a
CullC ((Bool -> Bool)
-> ReaderC Bool (NonDetC m) (ctx a)
-> ReaderC Bool (NonDetC m) (ctx a)
forall r (sig :: (* -> *) -> * -> *) (m :: * -> *) a.
Has (Reader r) sig m =>
(r -> r) -> m a -> m a
local (Bool -> Bool -> Bool
forall a b. a -> b -> a
const Bool
True) (CullC m (ctx a) -> ReaderC Bool (NonDetC m) (ctx a)
forall (m :: * -> *) a. CullC m a -> ReaderC Bool (NonDetC m) a
runCullC (ctx (n a) -> CullC m (ctx a)
Handler ctx n (CullC m)
hdl (n a
m n a -> ctx () -> ctx (n a)
forall (f :: * -> *) a b. Functor f => a -> f b -> f a
<$ ctx ()
ctx))))
    R (L (L Empty n a
Empty))  -> CullC m (ctx a)
forall (f :: * -> *) a. Alternative f => f a
empty
    R (L (R Choose n a
Choose)) -> ctx Bool -> CullC m (ctx Bool)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Bool
True Bool -> ctx () -> ctx Bool
forall (f :: * -> *) a b. Functor f => a -> f b -> f a
<$ ctx ()
ctx) CullC m (ctx Bool) -> CullC m (ctx Bool) -> CullC m (ctx Bool)
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> ctx Bool -> CullC m (ctx Bool)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Bool
False Bool -> ctx () -> ctx Bool
forall (f :: * -> *) a b. Functor f => a -> f b -> f a
<$ ctx ()
ctx)
    R (R sig n a
other)      -> ReaderC Bool (NonDetC m) (ctx a) -> CullC m (ctx a)
forall (m :: * -> *) a. ReaderC Bool (NonDetC m) a -> CullC m a
CullC (Handler ctx n (ReaderC Bool (NonDetC m))
-> (:+:) (Reader Bool) (NonDet :+: sig) n a
-> ctx ()
-> ReaderC Bool (NonDetC m) (ctx a)
forall (sig :: (* -> *) -> * -> *) (m :: * -> *) (ctx :: * -> *)
       (n :: * -> *) a.
(Algebra sig m, Functor ctx) =>
Handler ctx n m -> sig n a -> ctx () -> m (ctx a)
alg (CullC m (ctx x) -> ReaderC Bool (NonDetC m) (ctx x)
forall (m :: * -> *) a. CullC m a -> ReaderC Bool (NonDetC m) a
runCullC (CullC m (ctx x) -> ReaderC Bool (NonDetC m) (ctx x))
-> (ctx (n x) -> CullC m (ctx x))
-> ctx (n x)
-> ReaderC Bool (NonDetC m) (ctx x)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ctx (n x) -> CullC m (ctx x)
Handler ctx n (CullC m)
hdl) ((:+:) NonDet sig n a -> (:+:) (Reader Bool) (NonDet :+: sig) n a
forall (f :: (* -> *) -> * -> *) (g :: (* -> *) -> * -> *)
       (m :: * -> *) k.
g m k -> (:+:) f g m k
R (sig n a -> (:+:) NonDet sig n a
forall (f :: (* -> *) -> * -> *) (g :: (* -> *) -> * -> *)
       (m :: * -> *) k.
g m k -> (:+:) f g m k
R sig n a
other)) ctx ()
ctx)
  {-# INLINE alg #-}