{-# LANGUAGE DeriveFunctor, ExistentialQuantification, FlexibleContexts, FlexibleInstances, GeneralizedNewtypeDeriving, MultiParamTypeClasses, StandaloneDeriving, TypeOperators, UndecidableInstances #-}
module Control.Effect.Fresh
( -- * Fresh effect
  Fresh(..)
, fresh
, resetFresh
  -- * Fresh carrier
, runFresh
, FreshC(..)
  -- * Re-exports
, Carrier
, Member
, run
) where

import Control.Applicative (Alternative(..))
import Control.Effect.Carrier
import Control.Effect.State
import Control.Monad (MonadPlus(..))
import qualified Control.Monad.Fail as Fail
import Control.Monad.Fix
import Control.Monad.IO.Class
import Control.Monad.Trans.Class

data Fresh m k
  = Fresh (Int -> m k)
  | forall b . Reset (m b) (b -> m k)

deriving instance Functor m => Functor (Fresh m)

instance HFunctor Fresh where
  hmap :: (forall x. m x -> n x) -> Fresh m a -> Fresh n a
hmap f :: forall x. m x -> n x
f (Fresh   k :: Int -> m a
k) = (Int -> n a) -> Fresh n a
forall (m :: * -> *) k. (Int -> m k) -> Fresh m k
Fresh       (m a -> n a
forall x. m x -> n x
f (m a -> n a) -> (Int -> m a) -> Int -> n a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> m a
k)
  hmap f :: forall x. m x -> n x
f (Reset m :: m b
m k :: b -> m a
k) = n b -> (b -> n a) -> Fresh n a
forall (m :: * -> *) k b. m b -> (b -> m k) -> Fresh m k
Reset (m b -> n b
forall x. m x -> n x
f m b
m) (m a -> n a
forall x. m x -> n x
f (m a -> n a) -> (b -> m a) -> b -> n a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> m a
k)

instance Effect Fresh where
  handle :: f ()
-> (forall x. f (m x) -> n (f x)) -> Fresh m a -> Fresh n (f a)
handle state :: f ()
state handler :: forall x. f (m x) -> n (f x)
handler (Fresh   k :: Int -> m a
k) = (Int -> n (f a)) -> Fresh n (f a)
forall (m :: * -> *) k. (Int -> m k) -> Fresh m k
Fresh (f (m a) -> n (f a)
forall x. f (m x) -> n (f x)
handler (f (m a) -> n (f a)) -> (Int -> f (m a)) -> Int -> n (f a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (m a -> f () -> f (m a)
forall (f :: * -> *) a b. Functor f => a -> f b -> f a
<$ f ()
state) (m a -> f (m a)) -> (Int -> m a) -> Int -> f (m a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> m a
k)
  handle state :: f ()
state handler :: forall x. f (m x) -> n (f x)
handler (Reset m :: m b
m k :: b -> m a
k) = n (f b) -> (f b -> n (f a)) -> Fresh n (f a)
forall (m :: * -> *) k b. m b -> (b -> m k) -> Fresh m k
Reset (f (m b) -> n (f b)
forall x. f (m x) -> n (f x)
handler (m b
m m b -> f () -> f (m b)
forall (f :: * -> *) a b. Functor f => a -> f b -> f a
<$ f ()
state)) (f (m a) -> n (f a)
forall x. f (m x) -> n (f x)
handler (f (m a) -> n (f a)) -> (f b -> f (m a)) -> f b -> n (f a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (b -> m a) -> f b -> f (m a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap b -> m a
k)

-- | Produce a fresh (i.e. unique) 'Int'.
--
--   prop> run (runFresh (replicateM n fresh)) === nub (run (runFresh (replicateM n fresh)))
fresh :: (Member Fresh sig, Carrier sig m) => m Int
fresh :: m Int
fresh = Fresh m Int -> m Int
forall (effect :: (* -> *) -> * -> *) (sig :: (* -> *) -> * -> *)
       (m :: * -> *) a.
(Member effect sig, Carrier sig m) =>
effect m a -> m a
send ((Int -> m Int) -> Fresh m Int
forall (m :: * -> *) k. (Int -> m k) -> Fresh m k
Fresh Int -> m Int
forall (f :: * -> *) a. Applicative f => a -> f a
pure)

-- | Reset the fresh counter after running a computation.
--
--   prop> run (runFresh (resetFresh (replicateM m fresh) *> replicateM n fresh)) === run (runFresh (replicateM n fresh))
resetFresh :: (Member Fresh sig, Carrier sig m) => m a -> m a
resetFresh :: m a -> m a
resetFresh m :: m a
m = Fresh m a -> m a
forall (effect :: (* -> *) -> * -> *) (sig :: (* -> *) -> * -> *)
       (m :: * -> *) a.
(Member effect sig, Carrier sig m) =>
effect m a -> m a
send (m a -> (a -> m a) -> Fresh m a
forall (m :: * -> *) k b. m b -> (b -> m k) -> Fresh m k
Reset m a
m a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure)


-- | Run a 'Fresh' effect counting up from 0.
--
--   prop> run (runFresh (replicateM n fresh)) === [0..pred n]
--   prop> run (runFresh (replicateM n fresh *> pure b)) === b
runFresh :: Functor m => FreshC m a -> m a
runFresh :: FreshC m a -> m a
runFresh = Int -> StateC Int m a -> m a
forall s (m :: * -> *) a. Functor m => s -> StateC s m a -> m a
evalState 0 (StateC Int m a -> m a)
-> (FreshC m a -> StateC Int m a) -> FreshC m a -> m a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FreshC m a -> StateC Int m a
forall (m :: * -> *) a. FreshC m a -> StateC Int m a
runFreshC

newtype FreshC m a = FreshC { FreshC m a -> StateC Int m a
runFreshC :: StateC Int m a }
  deriving (Applicative (FreshC m)
FreshC m a
Applicative (FreshC m) =>
(forall a. FreshC m a)
-> (forall a. FreshC m a -> FreshC m a -> FreshC m a)
-> (forall a. FreshC m a -> FreshC m [a])
-> (forall a. FreshC m a -> FreshC m [a])
-> Alternative (FreshC m)
FreshC m a -> FreshC m a -> FreshC m a
FreshC m a -> FreshC m [a]
FreshC m a -> FreshC m [a]
forall a. FreshC m a
forall a. FreshC m a -> FreshC m [a]
forall a. FreshC m a -> FreshC m a -> FreshC m a
forall (f :: * -> *).
Applicative f =>
(forall a. f a)
-> (forall a. f a -> f a -> f a)
-> (forall a. f a -> f [a])
-> (forall a. f a -> f [a])
-> Alternative f
forall (m :: * -> *).
(Alternative m, Monad m) =>
Applicative (FreshC m)
forall (m :: * -> *) a. (Alternative m, Monad m) => FreshC m a
forall (m :: * -> *) a.
(Alternative m, Monad m) =>
FreshC m a -> FreshC m [a]
forall (m :: * -> *) a.
(Alternative m, Monad m) =>
FreshC m a -> FreshC m a -> FreshC m a
many :: FreshC m a -> FreshC m [a]
$cmany :: forall (m :: * -> *) a.
(Alternative m, Monad m) =>
FreshC m a -> FreshC m [a]
some :: FreshC m a -> FreshC m [a]
$csome :: forall (m :: * -> *) a.
(Alternative m, Monad m) =>
FreshC m a -> FreshC m [a]
<|> :: FreshC m a -> FreshC m a -> FreshC m a
$c<|> :: forall (m :: * -> *) a.
(Alternative m, Monad m) =>
FreshC m a -> FreshC m a -> FreshC m a
empty :: FreshC m a
$cempty :: forall (m :: * -> *) a. (Alternative m, Monad m) => FreshC m a
$cp1Alternative :: forall (m :: * -> *).
(Alternative m, Monad m) =>
Applicative (FreshC m)
Alternative, Functor (FreshC m)
a -> FreshC m a
Functor (FreshC m) =>
(forall a. a -> FreshC m a)
-> (forall a b. FreshC m (a -> b) -> FreshC m a -> FreshC m b)
-> (forall a b c.
    (a -> b -> c) -> FreshC m a -> FreshC m b -> FreshC m c)
-> (forall a b. FreshC m a -> FreshC m b -> FreshC m b)
-> (forall a b. FreshC m a -> FreshC m b -> FreshC m a)
-> Applicative (FreshC m)
FreshC m a -> FreshC m b -> FreshC m b
FreshC m a -> FreshC m b -> FreshC m a
FreshC m (a -> b) -> FreshC m a -> FreshC m b
(a -> b -> c) -> FreshC m a -> FreshC m b -> FreshC m c
forall a. a -> FreshC m a
forall a b. FreshC m a -> FreshC m b -> FreshC m a
forall a b. FreshC m a -> FreshC m b -> FreshC m b
forall a b. FreshC m (a -> b) -> FreshC m a -> FreshC m b
forall a b c.
(a -> b -> c) -> FreshC m a -> FreshC m b -> FreshC m c
forall (m :: * -> *). Monad m => Functor (FreshC m)
forall (m :: * -> *) a. Monad m => a -> FreshC m a
forall (m :: * -> *) a b.
Monad m =>
FreshC m a -> FreshC m b -> FreshC m a
forall (m :: * -> *) a b.
Monad m =>
FreshC m a -> FreshC m b -> FreshC m b
forall (m :: * -> *) a b.
Monad m =>
FreshC m (a -> b) -> FreshC m a -> FreshC m b
forall (m :: * -> *) a b c.
Monad m =>
(a -> b -> c) -> FreshC m a -> FreshC m b -> FreshC m c
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
<* :: FreshC m a -> FreshC m b -> FreshC m a
$c<* :: forall (m :: * -> *) a b.
Monad m =>
FreshC m a -> FreshC m b -> FreshC m a
*> :: FreshC m a -> FreshC m b -> FreshC m b
$c*> :: forall (m :: * -> *) a b.
Monad m =>
FreshC m a -> FreshC m b -> FreshC m b
liftA2 :: (a -> b -> c) -> FreshC m a -> FreshC m b -> FreshC m c
$cliftA2 :: forall (m :: * -> *) a b c.
Monad m =>
(a -> b -> c) -> FreshC m a -> FreshC m b -> FreshC m c
<*> :: FreshC m (a -> b) -> FreshC m a -> FreshC m b
$c<*> :: forall (m :: * -> *) a b.
Monad m =>
FreshC m (a -> b) -> FreshC m a -> FreshC m b
pure :: a -> FreshC m a
$cpure :: forall (m :: * -> *) a. Monad m => a -> FreshC m a
$cp1Applicative :: forall (m :: * -> *). Monad m => Functor (FreshC m)
Applicative, a -> FreshC m b -> FreshC m a
(a -> b) -> FreshC m a -> FreshC m b
(forall a b. (a -> b) -> FreshC m a -> FreshC m b)
-> (forall a b. a -> FreshC m b -> FreshC m a)
-> Functor (FreshC m)
forall a b. a -> FreshC m b -> FreshC m a
forall a b. (a -> b) -> FreshC m a -> FreshC m b
forall (m :: * -> *) a b.
Functor m =>
a -> FreshC m b -> FreshC m a
forall (m :: * -> *) a b.
Functor m =>
(a -> b) -> FreshC m a -> FreshC m b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> FreshC m b -> FreshC m a
$c<$ :: forall (m :: * -> *) a b.
Functor m =>
a -> FreshC m b -> FreshC m a
fmap :: (a -> b) -> FreshC m a -> FreshC m b
$cfmap :: forall (m :: * -> *) a b.
Functor m =>
(a -> b) -> FreshC m a -> FreshC m b
Functor, Applicative (FreshC m)
a -> FreshC m a
Applicative (FreshC m) =>
(forall a b. FreshC m a -> (a -> FreshC m b) -> FreshC m b)
-> (forall a b. FreshC m a -> FreshC m b -> FreshC m b)
-> (forall a. a -> FreshC m a)
-> Monad (FreshC m)
FreshC m a -> (a -> FreshC m b) -> FreshC m b
FreshC m a -> FreshC m b -> FreshC m b
forall a. a -> FreshC m a
forall a b. FreshC m a -> FreshC m b -> FreshC m b
forall a b. FreshC m a -> (a -> FreshC m b) -> FreshC m b
forall (m :: * -> *). Monad m => Applicative (FreshC m)
forall (m :: * -> *) a. Monad m => a -> FreshC m a
forall (m :: * -> *) a b.
Monad m =>
FreshC m a -> FreshC m b -> FreshC m b
forall (m :: * -> *) a b.
Monad m =>
FreshC m a -> (a -> FreshC m b) -> FreshC m b
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
return :: a -> FreshC m a
$creturn :: forall (m :: * -> *) a. Monad m => a -> FreshC m a
>> :: FreshC m a -> FreshC m b -> FreshC m b
$c>> :: forall (m :: * -> *) a b.
Monad m =>
FreshC m a -> FreshC m b -> FreshC m b
>>= :: FreshC m a -> (a -> FreshC m b) -> FreshC m b
$c>>= :: forall (m :: * -> *) a b.
Monad m =>
FreshC m a -> (a -> FreshC m b) -> FreshC m b
$cp1Monad :: forall (m :: * -> *). Monad m => Applicative (FreshC m)
Monad, Monad (FreshC m)
Monad (FreshC m) =>
(forall a. String -> FreshC m a) -> MonadFail (FreshC m)
String -> FreshC m a
forall a. String -> FreshC m a
forall (m :: * -> *).
Monad m =>
(forall a. String -> m a) -> MonadFail m
forall (m :: * -> *). MonadFail m => Monad (FreshC m)
forall (m :: * -> *) a. MonadFail m => String -> FreshC m a
fail :: String -> FreshC m a
$cfail :: forall (m :: * -> *) a. MonadFail m => String -> FreshC m a
$cp1MonadFail :: forall (m :: * -> *). MonadFail m => Monad (FreshC m)
Fail.MonadFail, Monad (FreshC m)
Monad (FreshC m) =>
(forall a. (a -> FreshC m a) -> FreshC m a) -> MonadFix (FreshC m)
(a -> FreshC m a) -> FreshC m a
forall a. (a -> FreshC m a) -> FreshC m a
forall (m :: * -> *).
Monad m =>
(forall a. (a -> m a) -> m a) -> MonadFix m
forall (m :: * -> *). MonadFix m => Monad (FreshC m)
forall (m :: * -> *) a.
MonadFix m =>
(a -> FreshC m a) -> FreshC m a
mfix :: (a -> FreshC m a) -> FreshC m a
$cmfix :: forall (m :: * -> *) a.
MonadFix m =>
(a -> FreshC m a) -> FreshC m a
$cp1MonadFix :: forall (m :: * -> *). MonadFix m => Monad (FreshC m)
MonadFix, Monad (FreshC m)
Monad (FreshC m) =>
(forall a. IO a -> FreshC m a) -> MonadIO (FreshC m)
IO a -> FreshC m a
forall a. IO a -> FreshC m a
forall (m :: * -> *).
Monad m =>
(forall a. IO a -> m a) -> MonadIO m
forall (m :: * -> *). MonadIO m => Monad (FreshC m)
forall (m :: * -> *) a. MonadIO m => IO a -> FreshC m a
liftIO :: IO a -> FreshC m a
$cliftIO :: forall (m :: * -> *) a. MonadIO m => IO a -> FreshC m a
$cp1MonadIO :: forall (m :: * -> *). MonadIO m => Monad (FreshC m)
MonadIO, Monad (FreshC m)
Alternative (FreshC m)
FreshC m a
(Alternative (FreshC m), Monad (FreshC m)) =>
(forall a. FreshC m a)
-> (forall a. FreshC m a -> FreshC m a -> FreshC m a)
-> MonadPlus (FreshC m)
FreshC m a -> FreshC m a -> FreshC m a
forall a. FreshC m a
forall a. FreshC m a -> FreshC m a -> FreshC m a
forall (m :: * -> *). (Alternative m, Monad m) => Monad (FreshC m)
forall (m :: * -> *).
(Alternative m, Monad m) =>
Alternative (FreshC m)
forall (m :: * -> *).
(Alternative m, Monad m) =>
(forall a. m a) -> (forall a. m a -> m a -> m a) -> MonadPlus m
forall (m :: * -> *) a. (Alternative m, Monad m) => FreshC m a
forall (m :: * -> *) a.
(Alternative m, Monad m) =>
FreshC m a -> FreshC m a -> FreshC m a
mplus :: FreshC m a -> FreshC m a -> FreshC m a
$cmplus :: forall (m :: * -> *) a.
(Alternative m, Monad m) =>
FreshC m a -> FreshC m a -> FreshC m a
mzero :: FreshC m a
$cmzero :: forall (m :: * -> *) a. (Alternative m, Monad m) => FreshC m a
$cp2MonadPlus :: forall (m :: * -> *). (Alternative m, Monad m) => Monad (FreshC m)
$cp1MonadPlus :: forall (m :: * -> *).
(Alternative m, Monad m) =>
Alternative (FreshC m)
MonadPlus, m a -> FreshC m a
(forall (m :: * -> *) a. Monad m => m a -> FreshC m a)
-> MonadTrans FreshC
forall (m :: * -> *) a. Monad m => m a -> FreshC m a
forall (t :: (* -> *) -> * -> *).
(forall (m :: * -> *) a. Monad m => m a -> t m a) -> MonadTrans t
lift :: m a -> FreshC m a
$clift :: forall (m :: * -> *) a. Monad m => m a -> FreshC m a
MonadTrans)

instance (Carrier sig m, Effect sig) => Carrier (Fresh :+: sig) (FreshC m) where
  eff :: (:+:) Fresh sig (FreshC m) a -> FreshC m a
eff (L (Fresh   k :: Int -> FreshC m a
k)) = StateC Int m a -> FreshC m a
forall (m :: * -> *) a. StateC Int m a -> FreshC m a
FreshC (StateC Int m a -> FreshC m a) -> StateC Int m a -> FreshC m a
forall a b. (a -> b) -> a -> b
$ do
    Int
i <- StateC Int m Int
forall s (sig :: (* -> *) -> * -> *) (m :: * -> *).
(Member (State s) sig, Carrier sig m) =>
m s
get
    Int -> StateC Int m ()
forall s (sig :: (* -> *) -> * -> *) (m :: * -> *).
(Member (State s) sig, Carrier sig m) =>
s -> m ()
put (Int -> Int
forall a. Enum a => a -> a
succ Int
i)
    FreshC m a -> StateC Int m a
forall (m :: * -> *) a. FreshC m a -> StateC Int m a
runFreshC (Int -> FreshC m a
k Int
i)
  eff (L (Reset m :: FreshC m b
m k :: b -> FreshC m a
k)) = StateC Int m a -> FreshC m a
forall (m :: * -> *) a. StateC Int m a -> FreshC m a
FreshC (StateC Int m a -> FreshC m a) -> StateC Int m a -> FreshC m a
forall a b. (a -> b) -> a -> b
$ do
    Int
i <- StateC Int m Int
forall s (sig :: (* -> *) -> * -> *) (m :: * -> *).
(Member (State s) sig, Carrier sig m) =>
m s
get
    b
a <- FreshC m b -> StateC Int m b
forall (m :: * -> *) a. FreshC m a -> StateC Int m a
runFreshC FreshC m b
m
    Int -> StateC Int m ()
forall s (sig :: (* -> *) -> * -> *) (m :: * -> *).
(Member (State s) sig, Carrier sig m) =>
s -> m ()
put (Int
i :: Int)
    FreshC m a -> StateC Int m a
forall (m :: * -> *) a. FreshC m a -> StateC Int m a
runFreshC (b -> FreshC m a
k b
a)
  eff (R other :: sig (FreshC m) a
other)       = StateC Int m a -> FreshC m a
forall (m :: * -> *) a. StateC Int m a -> FreshC m a
FreshC ((:+:) (State Int) sig (StateC Int m) a -> StateC Int m a
forall (sig :: (* -> *) -> * -> *) (m :: * -> *) a.
Carrier sig m =>
sig m a -> m a
eff (sig (StateC Int m) a -> (:+:) (State Int) sig (StateC Int m) a
forall (f :: (* -> *) -> * -> *) (g :: (* -> *) -> * -> *)
       (m :: * -> *) k.
g m k -> (:+:) f g m k
R (sig (FreshC m) a -> sig (StateC Int m) a
forall (sig :: (* -> *) -> * -> *) (f :: * -> *) (g :: * -> *) a.
(HFunctor sig, Functor f, Coercible f g) =>
sig f a -> sig g a
handleCoercible sig (FreshC m) a
other)))
  {-# INLINE eff #-}


-- $setup
-- >>> :seti -XFlexibleContexts
-- >>> import Test.QuickCheck
-- >>> import Control.Effect.Pure
-- >>> import Control.Monad (replicateM)
-- >>> import Data.List (nub)