-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Monads for free
--
-- Free monads are useful for many tree-like structures and domain
-- specific languages.
--
-- If f is a Functor then the free Monad on
-- f is the type of trees whose nodes are labeled with the
-- constructors of f. The word "free" is used in the sense of
-- "unrestricted" rather than "zero-cost": Free f makes no
-- constraining assumptions beyond those given by f and the
-- definition of Monad. As used here it is a standard term from
-- the mathematical theory of adjoint functors.
--
-- Cofree comonads are dual to free monads. They provide convenient ways
-- to talk about branching streams and rose-trees, and can be used to
-- annotate syntax trees. The cofree comonad can be seen as a stream
-- parameterized by a Functor that controls its branching factor.
--
-- More information on free monads, including examples, can be found in
-- the following blog posts:
-- http://comonad.com/reader/2008/monads-for-free/
-- http://comonad.com/reader/2011/free-monads-for-less/
@package free
@version 5
-- | Left distributive Alternative functors for free, based on a
-- design by Stijn van Drongelen.
module Control.Alternative.Free
newtype Alt f a
Alt :: [AltF f a] -> Alt f a
[alternatives] :: Alt f a -> [AltF f a]
data AltF f a
[Ap] :: f a -> Alt f (a -> b) -> AltF f b
[Pure] :: a -> AltF f a
-- | Given a natural transformation from f to g, this
-- gives a canonical monoidal natural transformation from Alt
-- f to g.
runAlt :: forall f g a. Alternative g => (forall x. f x -> g x) -> Alt f a -> g a
-- | A version of lift that can be used with any f.
liftAlt :: f a -> Alt f a
-- | Given a natural transformation from f to g this
-- gives a monoidal natural transformation from Alt f to Alt
-- g.
hoistAlt :: (forall a. f a -> g a) -> Alt f b -> Alt g b
instance GHC.Base.Functor (Control.Alternative.Free.AltF f)
instance GHC.Base.Functor (Control.Alternative.Free.Alt f)
instance GHC.Base.Applicative (Control.Alternative.Free.AltF f)
instance GHC.Base.Applicative (Control.Alternative.Free.Alt f)
instance Data.Functor.Bind.Class.Apply (Control.Alternative.Free.Alt f)
instance Data.Functor.Alt.Alt (Control.Alternative.Free.Alt f)
instance GHC.Base.Alternative (Control.Alternative.Free.Alt f)
instance Data.Semigroup.Semigroup (Control.Alternative.Free.Alt f a)
instance GHC.Base.Monoid (Control.Alternative.Free.Alt f a)
-- | Final encoding of free Alternative functors.
module Control.Alternative.Free.Final
-- | The free Alternative for any f.
newtype Alt f a
Alt :: (forall g. Alternative g => (forall x. f x -> g x) -> g a) -> Alt f a
[_runAlt] :: Alt f a -> forall g. Alternative g => (forall x. f x -> g x) -> g a
-- | Given a natural transformation from f to g, this
-- gives a canonical monoidal natural transformation from Alt
-- f to g.
runAlt :: forall f g a. Alternative g => (forall x. f x -> g x) -> Alt f a -> g a
-- | A version of lift that can be used with f.
liftAlt :: f a -> Alt f a
-- | Given a natural transformation from f to g this
-- gives a monoidal natural transformation from Alt f to Alt
-- g.
hoistAlt :: (forall a. f a -> g a) -> Alt f b -> Alt g b
instance GHC.Base.Functor (Control.Alternative.Free.Final.Alt f)
instance Data.Functor.Bind.Class.Apply (Control.Alternative.Free.Final.Alt f)
instance GHC.Base.Applicative (Control.Alternative.Free.Final.Alt f)
instance Data.Functor.Alt.Alt (Control.Alternative.Free.Final.Alt f)
instance GHC.Base.Alternative (Control.Alternative.Free.Final.Alt f)
instance Data.Semigroup.Semigroup (Control.Alternative.Free.Final.Alt f a)
instance GHC.Base.Monoid (Control.Alternative.Free.Final.Alt f a)
-- | Applicative functors for free
module Control.Applicative.Free
-- | The free Applicative for a Functor f.
data Ap f a
[Pure] :: a -> Ap f a
[Ap] :: f a -> Ap f (a -> b) -> Ap f b
-- | Given a natural transformation from f to g, this
-- gives a canonical monoidal natural transformation from Ap
-- f to g.
--
--
-- runAp t == retractApp . hoistApp t
--
runAp :: Applicative g => (forall x. f x -> g x) -> Ap f a -> g a
-- | Perform a monoidal analysis over free applicative value.
--
-- Example:
--
--
-- count :: Ap f a -> Int
-- count = getSum . runAp_ (\_ -> Sum 1)
--
runAp_ :: Monoid m => (forall a. f a -> m) -> Ap f b -> m
-- | A version of lift that can be used with just a Functor
-- for f.
liftAp :: f a -> Ap f a
-- | Tear down a free Applicative using iteration.
iterAp :: Functor g => (g a -> a) -> Ap g a -> a
-- | Given a natural transformation from f to g this
-- gives a monoidal natural transformation from Ap f to Ap
-- g.
hoistAp :: (forall a. f a -> g a) -> Ap f b -> Ap g b
-- | Interprets the free applicative functor over f using the semantics for
-- pure and <*> given by the Applicative instance for
-- f.
--
--
-- retractApp == runAp id
--
retractAp :: Applicative f => Ap f a -> f a
instance GHC.Base.Functor (Control.Applicative.Free.Ap f)
instance Data.Functor.Bind.Class.Apply (Control.Applicative.Free.Ap f)
instance GHC.Base.Applicative (Control.Applicative.Free.Ap f)
instance Control.Comonad.Comonad f => Control.Comonad.Comonad (Control.Applicative.Free.Ap f)
-- | A faster free applicative. Based on Dave Menendez's work.
module Control.Applicative.Free.Fast
-- | The free applicative is composed of a sequence of effects, and a pure
-- function to apply that sequence to. The fast free applicative
-- separates these from each other, so that the sequence may be built up
-- independently, and so that fmap can run in constant time by
-- having immediate access to the pure function.
data ASeq f a
[ANil] :: ASeq f ()
[ACons] :: f a -> ASeq f u -> ASeq f (a, u)
-- | Interprets the sequence of effects using the semantics for pure
-- and <*> given by the Applicative instance for f.
reduceASeq :: Applicative f => ASeq f u -> f u
-- | Given a natural transformation from f to g this
-- gives a natural transformation from ASeq f to ASeq
-- g.
hoistASeq :: (forall x. f x -> g x) -> ASeq f a -> ASeq g a
-- | Traverse a sequence with resepect to its interpretation type
-- f.
traverseASeq :: Applicative h => (forall x. f x -> h (g x)) -> ASeq f a -> h (ASeq g a)
-- | It may not be obvious, but this essentially acts like ++, traversing
-- the first sequence and creating a new one by appending the second
-- sequence. The difference is that this also has to modify the return
-- functions and that the return type depends on the input types.
--
-- See the source of hoistAp as an example usage.
rebaseASeq :: ASeq f u -> (forall x. (x -> y) -> ASeq f x -> z) -> (v -> u -> y) -> ASeq f v -> z
-- | The faster free Applicative.
newtype Ap f a
Ap :: (forall u y z. (forall x. (x -> y) -> ASeq f x -> z) -> (u -> a -> y) -> ASeq f u -> z) -> Ap f a
[unAp] :: Ap f a -> forall u y z. (forall x. (x -> y) -> ASeq f x -> z) -> (u -> a -> y) -> ASeq f u -> z
-- | A version of lift that can be used with just a Functor
-- for f.
liftAp :: f a -> Ap f a
-- | Interprets the free applicative functor over f using the semantics for
-- pure and <*> given by the Applicative instance for
-- f.
--
--
-- retractApp == runAp id
--
retractAp :: Applicative f => Ap f a -> f a
-- | Given a natural transformation from f to g, this
-- gives a canonical monoidal natural transformation from Ap
-- f to g.
--
--
-- runAp t == retractApp . hoistApp t
--
runAp :: Applicative g => (forall x. f x -> g x) -> Ap f a -> g a
-- | Perform a monoidal analysis over free applicative value.
--
-- Example:
--
--
-- count :: Ap f a -> Int
-- count = getSum . runAp_ (\_ -> Sum 1)
--
runAp_ :: Monoid m => (forall a. f a -> m) -> Ap f b -> m
-- | Given a natural transformation from f to g this
-- gives a monoidal natural transformation from Ap f to Ap
-- g.
hoistAp :: (forall x. f x -> g x) -> Ap f a -> Ap g a
instance GHC.Base.Functor (Control.Applicative.Free.Fast.Ap f)
instance Data.Functor.Bind.Class.Apply (Control.Applicative.Free.Fast.Ap f)
instance GHC.Base.Applicative (Control.Applicative.Free.Fast.Ap f)
-- | Final encoding of free Applicative functors.
module Control.Applicative.Free.Final
-- | The free Applicative for a Functor f.
newtype Ap f a
Ap :: (forall g. Applicative g => (forall x. f x -> g x) -> g a) -> Ap f a
[_runAp] :: Ap f a -> forall g. Applicative g => (forall x. f x -> g x) -> g a
-- | Given a natural transformation from f to g, this
-- gives a canonical monoidal natural transformation from Ap
-- f to g.
--
--
-- runAp t == retractApp . hoistApp t
--
runAp :: Applicative g => (forall x. f x -> g x) -> Ap f a -> g a
-- | Perform a monoidal analysis over free applicative value.
--
-- Example:
--
--
-- count :: Ap f a -> Int
-- count = getSum . runAp_ (\_ -> Sum 1)
--
runAp_ :: Monoid m => (forall a. f a -> m) -> Ap f b -> m
-- | A version of lift that can be used with just a Functor
-- for f.
liftAp :: f a -> Ap f a
-- | Given a natural transformation from f to g this
-- gives a monoidal natural transformation from Ap f to Ap
-- g.
hoistAp :: (forall a. f a -> g a) -> Ap f b -> Ap g b
-- | Interprets the free applicative functor over f using the semantics for
-- pure and <*> given by the Applicative instance for
-- f.
--
--
-- retractApp == runAp id
--
retractAp :: Applicative f => Ap f a -> f a
instance GHC.Base.Functor (Control.Applicative.Free.Final.Ap f)
instance Data.Functor.Bind.Class.Apply (Control.Applicative.Free.Final.Ap f)
instance GHC.Base.Applicative (Control.Applicative.Free.Final.Ap f)
-- | Applicative functor transformers for free
module Control.Applicative.Trans.Free
-- | The free Applicative transformer for a Functor
-- f over Applicative g.
newtype ApT f g a
ApT :: g (ApF f g a) -> ApT f g a
[getApT] :: ApT f g a -> g (ApF f g a)
-- | The free Applicative for a Functor f.
data ApF f g a
[Pure] :: a -> ApF f g a
[Ap] :: f a -> ApT f g (a -> b) -> ApF f g b
-- | A version of lift that can be used with no constraint for
-- f.
liftApT :: Applicative g => f a -> ApT f g a
-- | Lift an action of the "outer" Functor g a to
-- ApT f g a.
liftApO :: Functor g => g a -> ApT f g a
-- | Given natural transformations f ~> h and g . h ~>
-- h this gives a natural transformation ApT f g ~> h.
runApT :: (Applicative h, Functor g) => (forall a. f a -> h a) -> (forall a. g (h a) -> h a) -> ApT f g b -> h b
-- | Given natural transformations f ~> h and g . h ~>
-- h this gives a natural transformation ApF f g ~> h.
runApF :: (Applicative h, Functor g) => (forall a. f a -> h a) -> (forall a. g (h a) -> h a) -> ApF f g b -> h b
-- | Perform a monoidal analysis over ApT f g b value.
--
-- Examples:
--
--
-- height :: (Functor g, Foldable g) => ApT f g a -> Int
-- height = getSum . runApT_ (_ -> Sum 1) maximum
--
--
--
-- size :: (Functor g, Foldable g) => ApT f g a -> Int
-- size = getSum . runApT_ (_ -> Sum 1) fold
--
runApT_ :: (Functor g, Monoid m) => (forall a. f a -> m) -> (g m -> m) -> ApT f g b -> m
-- | Given a natural transformation from f to f' this
-- gives a monoidal natural transformation from ApT f g to
-- ApT f' g.
hoistApT :: Functor g => (forall a. f a -> f' a) -> ApT f g b -> ApT f' g b
-- | Given a natural transformation from f to f' this
-- gives a monoidal natural transformation from ApF f g to
-- ApF f' g.
hoistApF :: Functor g => (forall a. f a -> f' a) -> ApF f g b -> ApF f' g b
-- | Given a natural transformation from g to g' this
-- gives a monoidal natural transformation from ApT f g to
-- ApT f g'.
transApT :: Functor g => (forall a. g a -> g' a) -> ApT f g b -> ApT f g' b
-- | Given a natural transformation from g to g' this
-- gives a monoidal natural transformation from ApF f g to
-- ApF f g'.
transApF :: Functor g => (forall a. g a -> g' a) -> ApF f g b -> ApF f g' b
-- | Pull out and join m layers of ApT f m a.
joinApT :: Monad m => ApT f m a -> m (Ap f a)
-- | The free Applicative for a Functor f.
type Ap f = ApT f Identity
-- | Given a natural transformation from f to g, this
-- gives a canonical monoidal natural transformation from Ap
-- f to g.
--
--
-- runAp t == retractApp . hoistApp t
--
runAp :: Applicative g => (forall x. f x -> g x) -> Ap f a -> g a
-- | Perform a monoidal analysis over free applicative value.
--
-- Example:
--
--
-- count :: Ap f a -> Int
-- count = getSum . runAp_ (\_ -> Sum 1)
--
runAp_ :: Monoid m => (forall x. f x -> m) -> Ap f a -> m
-- | Interprets the free applicative functor over f using the semantics for
-- pure and <*> given by the Applicative instance for
-- f.
--
--
-- retractApp == runAp id
--
retractAp :: Applicative f => Ap f a -> f a
-- | The free Alternative for a Functor f.
type Alt f = ApT f []
-- | Given a natural transformation from f to g, this
-- gives a canonical monoidal natural transformation from Alt
-- f to g.
runAlt :: (Alternative g, Foldable t) => (forall x. f x -> g x) -> ApT f t a -> g a
instance GHC.Base.Functor g => GHC.Base.Functor (Control.Applicative.Trans.Free.ApF f g)
instance GHC.Base.Functor g => GHC.Base.Functor (Control.Applicative.Trans.Free.ApT f g)
instance GHC.Base.Applicative g => GHC.Base.Applicative (Control.Applicative.Trans.Free.ApF f g)
instance GHC.Base.Applicative g => GHC.Base.Applicative (Control.Applicative.Trans.Free.ApT f g)
instance GHC.Base.Applicative g => Data.Functor.Bind.Class.Apply (Control.Applicative.Trans.Free.ApF f g)
instance GHC.Base.Applicative g => Data.Functor.Bind.Class.Apply (Control.Applicative.Trans.Free.ApT f g)
instance GHC.Base.Alternative g => GHC.Base.Alternative (Control.Applicative.Trans.Free.ApT f g)
module Control.Comonad.Cofree.Class
-- | Allows you to peel a layer off a cofree comonad.
class (Functor f, Comonad w) => ComonadCofree f w | w -> f
-- | Remove a layer.
unwrap :: ComonadCofree f w => w a -> f (w a)
instance Control.Comonad.Cofree.Class.ComonadCofree GHC.Base.Maybe Data.List.NonEmpty.NonEmpty
instance Control.Comonad.Cofree.Class.ComonadCofree [] Data.Tree.Tree
instance Control.Comonad.Cofree.Class.ComonadCofree (Data.Functor.Const.Const b) ((,) b)
instance Control.Comonad.Cofree.Class.ComonadCofree f w => Control.Comonad.Cofree.Class.ComonadCofree f (Control.Monad.Trans.Identity.IdentityT w)
instance Control.Comonad.Cofree.Class.ComonadCofree f w => Control.Comonad.Cofree.Class.ComonadCofree f (Control.Comonad.Trans.Env.EnvT e w)
instance Control.Comonad.Cofree.Class.ComonadCofree f w => Control.Comonad.Cofree.Class.ComonadCofree f (Control.Comonad.Trans.Store.StoreT s w)
instance (Control.Comonad.Cofree.Class.ComonadCofree f w, GHC.Base.Monoid m) => Control.Comonad.Cofree.Class.ComonadCofree f (Control.Comonad.Trans.Traced.TracedT m w)
-- | The cofree comonad transformer
module Control.Comonad.Trans.Cofree
-- | This is a cofree comonad of some functor f, with a comonad
-- w threaded through it at each level.
newtype CofreeT f w a
CofreeT :: w (CofreeF f a (CofreeT f w a)) -> CofreeT f w a
[runCofreeT] :: CofreeT f w a -> w (CofreeF f a (CofreeT f w a))
-- | The cofree Comonad of a functor f.
type Cofree f = CofreeT f Identity
-- | Wrap another layer around a cofree comonad value.
--
-- cofree is a right inverse of runCofree.
--
--
-- runCofree . cofree == id
--
cofree :: CofreeF f a (Cofree f a) -> Cofree f a
-- | Unpeel the first layer off a cofree comonad value.
--
-- runCofree is a right inverse of cofree.
--
--
-- cofree . runCofree == id
--
runCofree :: Cofree f a -> CofreeF f a (Cofree f a)
-- | This is the base functor of the cofree comonad transformer.
data CofreeF f a b
(:<) :: a -> f b -> CofreeF f a b
-- | Allows you to peel a layer off a cofree comonad.
class (Functor f, Comonad w) => ComonadCofree f w | w -> f
-- | Remove a layer.
unwrap :: ComonadCofree f w => w a -> f (w a)
-- | Extract the head of the base functor
headF :: CofreeF f a b -> a
-- | Extract the tails of the base functor
tailF :: CofreeF f a b -> f b
-- | Lift a natural transformation from f to g into a
-- comonad homomorphism from CofreeT f w to
-- CofreeT g w
transCofreeT :: (Functor g, Comonad w) => (forall x. f x -> g x) -> CofreeT f w a -> CofreeT g w a
-- | Unfold a CofreeT comonad transformer from a coalgebra and an
-- initial comonad.
coiterT :: (Functor f, Comonad w) => (w a -> f (w a)) -> w a -> CofreeT f w a
instance (GHC.Read.Read (f b), GHC.Read.Read a) => GHC.Read.Read (Control.Comonad.Trans.Cofree.CofreeF f a b)
instance (GHC.Show.Show (f b), GHC.Show.Show a) => GHC.Show.Show (Control.Comonad.Trans.Cofree.CofreeF f a b)
instance (GHC.Classes.Ord (f b), GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Comonad.Trans.Cofree.CofreeF f a b)
instance (GHC.Classes.Eq (f b), GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Comonad.Trans.Cofree.CofreeF f a b)
instance (GHC.Base.Functor f, GHC.Base.Functor w) => GHC.Base.Functor (Control.Comonad.Trans.Cofree.CofreeT f w)
instance (GHC.Base.Functor f, Control.Comonad.Comonad w) => Control.Comonad.Comonad (Control.Comonad.Trans.Cofree.CofreeT f w)
instance (Data.Foldable.Foldable f, Data.Foldable.Foldable w) => Data.Foldable.Foldable (Control.Comonad.Trans.Cofree.CofreeT f w)
instance (Data.Traversable.Traversable f, Data.Traversable.Traversable w) => Data.Traversable.Traversable (Control.Comonad.Trans.Cofree.CofreeT f w)
instance Control.Comonad.Trans.Class.ComonadTrans (Control.Comonad.Trans.Cofree.CofreeT f)
instance (GHC.Base.Functor f, Control.Comonad.Comonad w) => Control.Comonad.Cofree.Class.ComonadCofree f (Control.Comonad.Trans.Cofree.CofreeT f w)
instance (GHC.Base.Functor f, Control.Comonad.Env.Class.ComonadEnv e w) => Control.Comonad.Env.Class.ComonadEnv e (Control.Comonad.Trans.Cofree.CofreeT f w)
instance GHC.Base.Functor f => Control.Comonad.Hoist.Class.ComonadHoist (Control.Comonad.Trans.Cofree.CofreeT f)
instance GHC.Show.Show (w (Control.Comonad.Trans.Cofree.CofreeF f a (Control.Comonad.Trans.Cofree.CofreeT f w a))) => GHC.Show.Show (Control.Comonad.Trans.Cofree.CofreeT f w a)
instance GHC.Read.Read (w (Control.Comonad.Trans.Cofree.CofreeF f a (Control.Comonad.Trans.Cofree.CofreeT f w a))) => GHC.Read.Read (Control.Comonad.Trans.Cofree.CofreeT f w a)
instance GHC.Classes.Eq (w (Control.Comonad.Trans.Cofree.CofreeF f a (Control.Comonad.Trans.Cofree.CofreeT f w a))) => GHC.Classes.Eq (Control.Comonad.Trans.Cofree.CofreeT f w a)
instance GHC.Classes.Ord (w (Control.Comonad.Trans.Cofree.CofreeF f a (Control.Comonad.Trans.Cofree.CofreeT f w a))) => GHC.Classes.Ord (Control.Comonad.Trans.Cofree.CofreeT f w a)
instance (GHC.Base.Alternative f, GHC.Base.Monad w) => GHC.Base.Monad (Control.Comonad.Trans.Cofree.CofreeT f w)
instance (GHC.Base.Alternative f, GHC.Base.Applicative w) => GHC.Base.Applicative (Control.Comonad.Trans.Cofree.CofreeT f w)
instance GHC.Base.Alternative f => Control.Monad.Trans.Class.MonadTrans (Control.Comonad.Trans.Cofree.CofreeT f)
instance (GHC.Base.Alternative f, Control.Monad.Zip.MonadZip f, Control.Monad.Zip.MonadZip m) => Control.Monad.Zip.MonadZip (Control.Comonad.Trans.Cofree.CofreeT f m)
instance (Data.Typeable.Internal.Typeable f, Data.Typeable.Internal.Typeable w, Data.Typeable.Internal.Typeable a, Data.Data.Data (w (Control.Comonad.Trans.Cofree.CofreeF f a (Control.Comonad.Trans.Cofree.CofreeT f w a))), Data.Data.Data a) => Data.Data.Data (Control.Comonad.Trans.Cofree.CofreeT f w a)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Comonad.Trans.Cofree.CofreeF f a)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Comonad.Trans.Cofree.CofreeF f a)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Comonad.Trans.Cofree.CofreeF f a)
instance GHC.Base.Functor f => Data.Bifunctor.Bifunctor (Control.Comonad.Trans.Cofree.CofreeF f)
instance Data.Foldable.Foldable f => Data.Bifoldable.Bifoldable (Control.Comonad.Trans.Cofree.CofreeF f)
instance Data.Traversable.Traversable f => Data.Bitraversable.Bitraversable (Control.Comonad.Trans.Cofree.CofreeF f)
instance (Data.Typeable.Internal.Typeable f, Data.Typeable.Internal.Typeable a, Data.Typeable.Internal.Typeable b, Data.Data.Data a, Data.Data.Data (f b), Data.Data.Data b) => Data.Data.Data (Control.Comonad.Trans.Cofree.CofreeF f a b)
-- | Monads for free.
module Control.Monad.Free.Class
-- | Monads provide substitution (fmap) and renormalization
-- (join):
--
--
-- m >>= f = join (fmap f m)
--
--
-- A free Monad is one that does no work during the normalization
-- step beyond simply grafting the two monadic values together.
--
-- [] is not a free Monad (in this sense) because
-- join [[a]] smashes the lists flat.
--
-- On the other hand, consider:
--
--
-- data Tree a = Bin (Tree a) (Tree a) | Tip a
--
--
--
-- instance Monad Tree where
-- return = Tip
-- Tip a >>= f = f a
-- Bin l r >>= f = Bin (l >>= f) (r >>= f)
--
--
-- This Monad is the free Monad of Pair:
--
--
-- data Pair a = Pair a a
--
--
-- And we could make an instance of MonadFree for it directly:
--
--
-- instance MonadFree Pair Tree where
-- wrap (Pair l r) = Bin l r
--
--
-- Or we could choose to program with Free Pair instead
-- of Tree and thereby avoid having to define our own
-- Monad instance.
--
-- Moreover, Control.Monad.Free.Church provides a MonadFree
-- instance that can improve the asymptotic complexity of code
-- that constructs free monads by effectively reassociating the use of
-- (>>=). You may also want to take a look at the
-- kan-extensions package
-- (http://hackage.haskell.org/package/kan-extensions).
--
-- See Free for a more formal definition of the free Monad
-- for a Functor.
class Monad m => MonadFree f m | m -> f
-- | Add a layer.
--
--
-- wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--
wrap :: MonadFree f m => f (m a) -> m a
-- | Add a layer.
--
--
-- wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--
wrap :: (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a
-- | A version of lift that can be used with just a Functor for f.
liftF :: (Functor f, MonadFree f m) => f a -> m a
-- | A version of wrap for monad transformers over a free monad.
--
-- Note: that this is the default implementation for wrap
-- for MonadFree f (t m).
wrapT :: (Functor f, MonadFree f m, MonadTrans t, Monad (t m)) => f (t m a) -> t m a
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Reader.ReaderT e m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.State.Lazy.StateT s m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.State.Strict.StateT s m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Cont.ContT r m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m, GHC.Base.Monoid w) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Writer.Lazy.WriterT w m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m, GHC.Base.Monoid w) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Writer.Strict.WriterT w m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m, GHC.Base.Monoid w) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.RWS.Strict.RWST r w s m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m, GHC.Base.Monoid w) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.RWS.Lazy.RWST r w s m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Maybe.MaybeT m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Identity.IdentityT m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.List.ListT m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m, Control.Monad.Trans.Error.Error e) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Error.ErrorT e m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Except.ExceptT e m)
-- | Automatic generation of free monadic actions.
module Control.Monad.Free.TH
-- | $(makeFree ''T) provides free monadic actions for the
-- constructors of the given data type T.
makeFree :: Name -> Q [Dec]
-- | Like makeFree, but does not provide type signatures. This can
-- be used to attach Haddock comments to individual arguments for each
-- generated function.
--
--
-- data LangF x = Output String x
--
-- makeFree_ 'LangF
--
-- -- | Output a string.
-- output :: MonadFree LangF m =>
-- String -- ^ String to output.
-- -> m () -- ^ No result.
--
--
-- makeFree_ must be called *before* the explicit type signatures.
makeFree_ :: Name -> Q [Dec]
-- | $(makeFreeCon 'Con) provides free monadic action for a
-- data constructor Con. Note that you can attach Haddock
-- comment to the generated function by placing it before the top-level
-- invocation of makeFreeCon:
--
--
-- -- | Output a string.
-- makeFreeCon 'Output
--
makeFreeCon :: Name -> Q [Dec]
-- | Like makeFreeCon, but does not provide a type signature. This
-- can be used to attach Haddock comments to individual arguments.
--
--
-- data LangF x = Output String x
--
-- makeFreeCon_ 'Output
--
-- -- | Output a string.
-- output :: MonadFree LangF m =>
-- String -- ^ String to output.
-- -> m () -- ^ No result.
--
--
-- makeFreeCon_ must be called *before* the explicit type
-- signature.
makeFreeCon_ :: Name -> Q [Dec]
instance GHC.Show.Show Control.Monad.Free.TH.Arg
-- | Based on Capretta's Iterative Monad Transformer
--
-- Unlike Free, this is a true monad transformer.
module Control.Monad.Trans.Iter
-- | The monad supporting iteration based over a base monad m.
--
--
-- IterT ~ FreeT Identity
--
newtype IterT m a
IterT :: m (Either a (IterT m a)) -> IterT m a
[runIterT] :: IterT m a -> m (Either a (IterT m a))
-- | Plain iterative computations.
type Iter = IterT Identity
-- | Builds an iterative computation from one first step.
--
--
-- runIter . iter == id
--
iter :: Either a (Iter a) -> Iter a
-- | Executes the first step of an iterative computation
--
--
-- iter . runIter == id
--
runIter :: Iter a -> Either a (Iter a)
-- | Adds an extra layer to a free monad value.
--
-- In particular, for the iterative monad Iter, this makes the
-- computation require one more step, without changing its final result.
--
--
-- runIter (delay ma) == Right ma
--
delay :: (Monad f, MonadFree f m) => m a -> m a
-- | Lift a monad homomorphism from m to n into a Monad
-- homomorphism from IterT m to IterT n.
hoistIterT :: Monad n => (forall a. m a -> n a) -> IterT m b -> IterT n b
-- | Lifts a plain, non-terminating computation into a richer environment.
-- liftIter is a Monad homomorphism.
liftIter :: (Monad m) => Iter a -> IterT m a
-- | Cuts off an iterative computation after a given number of steps. If
-- the number of steps is 0 or less, no computation nor monadic effects
-- will take place.
--
-- The step where the final value is produced also counts towards the
-- limit.
--
-- Some examples (n ≥ 0):
--
--
-- cutoff 0 _ ≡ return Nothing
-- cutoff (n+1) . return ≡ return . Just
-- cutoff (n+1) . lift ≡ lift . liftM Just
-- cutoff (n+1) . delay ≡ delay . cutoff n
-- cutoff n never ≡ iterate delay (return Nothing) !! n
--
--
-- Calling retract . cutoff n is always
-- terminating, provided each of the steps in the iteration is
-- terminating.
cutoff :: (Monad m) => Integer -> IterT m a -> IterT m (Maybe a)
-- | A computation that never terminates
never :: (Monad f, MonadFree f m) => m a
-- | Repeatedly run a computation until it produces a Just value.
-- This can be useful when paired with a monad that has side effects.
--
-- For example, we may have genId :: IO (Maybe Id) that uses a
-- random number generator to allocate ids, but fails if it finds a
-- collision. We can repeatedly run this with
--
--
-- retract (untilJust genId) :: IO Id
--
untilJust :: (Monad m) => m (Maybe a) -> IterT m a
-- | Interleaves the steps of a finite list of iterative computations, and
-- collects their results.
--
-- The resulting computation has as many steps as the longest computation
-- in the list.
interleave :: Monad m => [IterT m a] -> IterT m [a]
-- | Interleaves the steps of a finite list of computations, and discards
-- their results.
--
-- The resulting computation has as many steps as the longest computation
-- in the list.
--
-- Equivalent to void . interleave.
interleave_ :: (Monad m) => [IterT m a] -> IterT m ()
-- | retract is the left inverse of lift
--
--
-- retract . lift = id
--
retract :: Monad m => IterT m a -> m a
-- | Tear down a Free Monad using iteration.
fold :: Monad m => (m a -> a) -> IterT m a -> a
-- | Like fold with monadic result.
foldM :: (Monad m, Monad n) => (m (n a) -> n a) -> IterT m a -> n a
-- | Monads provide substitution (fmap) and renormalization
-- (join):
--
--
-- m >>= f = join (fmap f m)
--
--
-- A free Monad is one that does no work during the normalization
-- step beyond simply grafting the two monadic values together.
--
-- [] is not a free Monad (in this sense) because
-- join [[a]] smashes the lists flat.
--
-- On the other hand, consider:
--
--
-- data Tree a = Bin (Tree a) (Tree a) | Tip a
--
--
--
-- instance Monad Tree where
-- return = Tip
-- Tip a >>= f = f a
-- Bin l r >>= f = Bin (l >>= f) (r >>= f)
--
--
-- This Monad is the free Monad of Pair:
--
--
-- data Pair a = Pair a a
--
--
-- And we could make an instance of MonadFree for it directly:
--
--
-- instance MonadFree Pair Tree where
-- wrap (Pair l r) = Bin l r
--
--
-- Or we could choose to program with Free Pair instead
-- of Tree and thereby avoid having to define our own
-- Monad instance.
--
-- Moreover, Control.Monad.Free.Church provides a MonadFree
-- instance that can improve the asymptotic complexity of code
-- that constructs free monads by effectively reassociating the use of
-- (>>=). You may also want to take a look at the
-- kan-extensions package
-- (http://hackage.haskell.org/package/kan-extensions).
--
-- See Free for a more formal definition of the free Monad
-- for a Functor.
class Monad m => MonadFree f m | m -> f
-- | Add a layer.
--
--
-- wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--
wrap :: MonadFree f m => f (m a) -> m a
-- | Add a layer.
--
--
-- wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--
wrap :: (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a
instance Data.Functor.Classes.Eq1 m => Data.Functor.Classes.Eq1 (Control.Monad.Trans.Iter.IterT m)
instance (Data.Functor.Classes.Eq1 m, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Trans.Iter.IterT m a)
instance Data.Functor.Classes.Ord1 m => Data.Functor.Classes.Ord1 (Control.Monad.Trans.Iter.IterT m)
instance (Data.Functor.Classes.Ord1 m, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Trans.Iter.IterT m a)
instance Data.Functor.Classes.Show1 m => Data.Functor.Classes.Show1 (Control.Monad.Trans.Iter.IterT m)
instance (Data.Functor.Classes.Show1 m, GHC.Show.Show a) => GHC.Show.Show (Control.Monad.Trans.Iter.IterT m a)
instance Data.Functor.Classes.Read1 m => Data.Functor.Classes.Read1 (Control.Monad.Trans.Iter.IterT m)
instance (Data.Functor.Classes.Read1 m, GHC.Read.Read a) => GHC.Read.Read (Control.Monad.Trans.Iter.IterT m a)
instance GHC.Base.Monad m => GHC.Base.Functor (Control.Monad.Trans.Iter.IterT m)
instance GHC.Base.Monad m => GHC.Base.Applicative (Control.Monad.Trans.Iter.IterT m)
instance GHC.Base.Monad m => GHC.Base.Monad (Control.Monad.Trans.Iter.IterT m)
instance GHC.Base.Monad m => Control.Monad.Fail.MonadFail (Control.Monad.Trans.Iter.IterT m)
instance GHC.Base.Monad m => Data.Functor.Bind.Class.Apply (Control.Monad.Trans.Iter.IterT m)
instance GHC.Base.Monad m => Data.Functor.Bind.Class.Bind (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.Fix.MonadFix m => Control.Monad.Fix.MonadFix (Control.Monad.Trans.Iter.IterT m)
instance GHC.Base.Monad m => GHC.Base.Alternative (Control.Monad.Trans.Iter.IterT m)
instance GHC.Base.Monad m => GHC.Base.MonadPlus (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.Trans.Class.MonadTrans Control.Monad.Trans.Iter.IterT
instance Data.Foldable.Foldable m => Data.Foldable.Foldable (Control.Monad.Trans.Iter.IterT m)
instance Data.Semigroup.Foldable.Class.Foldable1 m => Data.Semigroup.Foldable.Class.Foldable1 (Control.Monad.Trans.Iter.IterT m)
instance (GHC.Base.Monad m, Data.Traversable.Traversable m) => Data.Traversable.Traversable (Control.Monad.Trans.Iter.IterT m)
instance (GHC.Base.Monad m, Data.Semigroup.Traversable.Class.Traversable1 m) => Data.Semigroup.Traversable.Class.Traversable1 (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.Reader.Class.MonadReader e m => Control.Monad.Reader.Class.MonadReader e (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.Writer.Class.MonadWriter w m => Control.Monad.Writer.Class.MonadWriter w (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.State.Class.MonadState s m => Control.Monad.State.Class.MonadState s (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.Error.Class.MonadError e m => Control.Monad.Error.Class.MonadError e (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.IO.Class.MonadIO m => Control.Monad.IO.Class.MonadIO (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.Cont.Class.MonadCont m => Control.Monad.Cont.Class.MonadCont (Control.Monad.Trans.Iter.IterT m)
instance GHC.Base.Monad m => Control.Monad.Free.Class.MonadFree Data.Functor.Identity.Identity (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.Catch.MonadThrow m => Control.Monad.Catch.MonadThrow (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.Catch.MonadCatch m => Control.Monad.Catch.MonadCatch (Control.Monad.Trans.Iter.IterT m)
instance (GHC.Base.Monad m, Data.Semigroup.Semigroup a, GHC.Base.Monoid a) => GHC.Base.Monoid (Control.Monad.Trans.Iter.IterT m a)
instance (GHC.Base.Monad m, Data.Semigroup.Semigroup a) => Data.Semigroup.Semigroup (Control.Monad.Trans.Iter.IterT m a)
instance (Data.Typeable.Internal.Typeable m, Data.Typeable.Internal.Typeable a, Data.Data.Data (m (Data.Either.Either a (Control.Monad.Trans.Iter.IterT m a))), Data.Data.Data a) => Data.Data.Data (Control.Monad.Trans.Iter.IterT m a)
-- | Given an applicative, the free monad transformer.
module Control.Monad.Trans.Free.Ap
-- | The base functor for a free monad.
data FreeF f a b
Pure :: a -> FreeF f a b
Free :: (f b) -> FreeF f a b
-- | The "free monad transformer" for an applicative f
newtype FreeT f m a
FreeT :: m (FreeF f a (FreeT f m a)) -> FreeT f m a
[runFreeT] :: FreeT f m a -> m (FreeF f a (FreeT f m a))
-- | The "free monad" for an applicative f.
type Free f = FreeT f Identity
-- | Pushes a layer into a free monad value.
free :: FreeF f a (Free f a) -> Free f a
-- | Evaluates the first layer out of a free monad value.
runFree :: Free f a -> FreeF f a (Free f a)
-- | A version of lift that can be used with just a Functor for f.
liftF :: (Functor f, MonadFree f m) => f a -> m a
-- | Given an applicative homomorphism from f (m a) to m
-- a, tear down a free monad transformer using iteration.
iterT :: (Applicative f, Monad m) => (f (m a) -> m a) -> FreeT f m a -> m a
-- | Given an applicative homomorphism from f (t m a) to t m
-- a, tear down a free monad transformer using iteration over a
-- transformer.
iterTM :: (Applicative f, Monad m, MonadTrans t, Monad (t m)) => (f (t m a) -> t m a) -> FreeT f m a -> t m a
-- | Lift a monad homomorphism from m to n into a monad
-- homomorphism from FreeT f m to FreeT f
-- n
--
--
-- hoistFreeT :: (Monad m, Functor f) => (m ~> n) -> FreeT f m ~> FreeT f n
--
hoistFreeT :: (Monad m, Applicative f) => (forall a. m a -> n a) -> FreeT f m b -> FreeT f n b
-- | Lift an applicative homomorphism from f to g into a
-- monad homomorphism from FreeT f m to FreeT
-- g m
transFreeT :: (Monad m, Applicative g) => (forall a. f a -> g a) -> FreeT f m b -> FreeT g m b
-- | Pull out and join m layers of FreeT f m a.
joinFreeT :: (Monad m, Traversable f, Applicative f) => FreeT f m a -> m (Free f a)
-- | Cuts off a tree of computations at a given depth. If the depth is
-- 0 or less, no computation nor monadic effects will take
-- place.
--
-- Some examples (n ≥ 0):
--
--
-- cutoff 0 _ ≡ return Nothing
-- cutoff (n+1) . return ≡ return . Just
-- cutoff (n+1) . lift ≡ lift . liftM Just
-- cutoff (n+1) . wrap ≡ wrap . fmap (cutoff n)
--
--
-- Calling retract . cutoff n is always
-- terminating, provided each of the steps in the iteration is
-- terminating.
cutoff :: (Applicative f, Applicative m, Monad m) => Integer -> FreeT f m a -> FreeT f m (Maybe a)
-- | partialIterT n phi m interprets first n layers of
-- m using phi. This is sort of the opposite for
-- cutoff.
--
-- Some examples (n ≥ 0):
--
--
-- partialIterT 0 _ m ≡ m
-- partialIterT (n+1) phi . return ≡ return
-- partialIterT (n+1) phi . lift ≡ lift
-- partialIterT (n+1) phi . wrap ≡ join . lift . phi
--
partialIterT :: Monad m => Integer -> (forall a. f a -> m a) -> FreeT f m b -> FreeT f m b
-- | intersperseT f m inserts a layer f between every two
-- layers in m.
--
--
-- intersperseT f . return ≡ return
-- intersperseT f . lift ≡ lift
-- intersperseT f . wrap ≡ wrap . fmap (iterTM (wrap . (<$ f) . wrap))
--
intersperseT :: (Monad m, Applicative m, Applicative f) => f a -> FreeT f m b -> FreeT f m b
-- | intercalateT f m inserts a layer f between every two
-- layers in m and then retracts the result.
--
--
-- intercalateT f ≡ retractT . intersperseT f
--
intercalateT :: (Monad m, MonadTrans t, Monad (t m)) => t m a -> FreeT (t m) m b -> t m b
-- | Tear down a free monad transformer using Monad instance for t
-- m.
retractT :: (MonadTrans t, Monad (t m), Monad m) => FreeT (t m) m a -> t m a
-- | retract is the left inverse of liftF
--
--
-- retract . liftF = id
--
retract :: Monad f => Free f a -> f a
-- | Given an applicative homomorphism from f to Identity,
-- tear down a Free Monad using iteration.
iter :: Applicative f => (f a -> a) -> Free f a -> a
-- | Like iter for monadic values.
iterM :: (Applicative f, Monad m) => (f (m a) -> m a) -> Free f a -> m a
-- | Monads provide substitution (fmap) and renormalization
-- (join):
--
--
-- m >>= f = join (fmap f m)
--
--
-- A free Monad is one that does no work during the normalization
-- step beyond simply grafting the two monadic values together.
--
-- [] is not a free Monad (in this sense) because
-- join [[a]] smashes the lists flat.
--
-- On the other hand, consider:
--
--
-- data Tree a = Bin (Tree a) (Tree a) | Tip a
--
--
--
-- instance Monad Tree where
-- return = Tip
-- Tip a >>= f = f a
-- Bin l r >>= f = Bin (l >>= f) (r >>= f)
--
--
-- This Monad is the free Monad of Pair:
--
--
-- data Pair a = Pair a a
--
--
-- And we could make an instance of MonadFree for it directly:
--
--
-- instance MonadFree Pair Tree where
-- wrap (Pair l r) = Bin l r
--
--
-- Or we could choose to program with Free Pair instead
-- of Tree and thereby avoid having to define our own
-- Monad instance.
--
-- Moreover, Control.Monad.Free.Church provides a MonadFree
-- instance that can improve the asymptotic complexity of code
-- that constructs free monads by effectively reassociating the use of
-- (>>=). You may also want to take a look at the
-- kan-extensions package
-- (http://hackage.haskell.org/package/kan-extensions).
--
-- See Free for a more formal definition of the free Monad
-- for a Functor.
class Monad m => MonadFree f m | m -> f
-- | Add a layer.
--
--
-- wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--
wrap :: MonadFree f m => f (m a) -> m a
-- | Add a layer.
--
--
-- wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--
wrap :: (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a
instance (GHC.Read.Read (f b), GHC.Read.Read a) => GHC.Read.Read (Control.Monad.Trans.Free.Ap.FreeF f a b)
instance (GHC.Show.Show (f b), GHC.Show.Show a) => GHC.Show.Show (Control.Monad.Trans.Free.Ap.FreeF f a b)
instance (GHC.Classes.Ord (f b), GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Trans.Free.Ap.FreeF f a b)
instance (GHC.Classes.Eq (f b), GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Trans.Free.Ap.FreeF f a b)
instance (Data.Functor.Classes.Eq1 f, Data.Functor.Classes.Eq1 m, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Trans.Free.Ap.FreeT f m a)
instance (Data.Functor.Classes.Eq1 f, Data.Functor.Classes.Eq1 m) => Data.Functor.Classes.Eq1 (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (Data.Functor.Classes.Ord1 f, Data.Functor.Classes.Ord1 m, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Trans.Free.Ap.FreeT f m a)
instance (Data.Functor.Classes.Ord1 f, Data.Functor.Classes.Ord1 m) => Data.Functor.Classes.Ord1 (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (Data.Functor.Classes.Show1 f, Data.Functor.Classes.Show1 m) => Data.Functor.Classes.Show1 (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (Data.Functor.Classes.Show1 f, Data.Functor.Classes.Show1 m, GHC.Show.Show a) => GHC.Show.Show (Control.Monad.Trans.Free.Ap.FreeT f m a)
instance (Data.Functor.Classes.Read1 f, Data.Functor.Classes.Read1 m) => Data.Functor.Classes.Read1 (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (Data.Functor.Classes.Read1 f, Data.Functor.Classes.Read1 m, GHC.Read.Read a) => GHC.Read.Read (Control.Monad.Trans.Free.Ap.FreeT f m a)
instance (GHC.Base.Functor f, GHC.Base.Monad m) => GHC.Base.Functor (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Base.Applicative f, GHC.Base.Applicative m, GHC.Base.Monad m) => GHC.Base.Applicative (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (Data.Functor.Bind.Class.Apply f, Data.Functor.Bind.Class.Apply m, GHC.Base.Monad m) => Data.Functor.Bind.Class.Apply (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (Data.Functor.Bind.Class.Apply f, Data.Functor.Bind.Class.Apply m, GHC.Base.Monad m) => Data.Functor.Bind.Class.Bind (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Base.Applicative f, GHC.Base.Applicative m, GHC.Base.Monad m) => GHC.Base.Monad (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Base.Applicative f, GHC.Base.Applicative m, GHC.Base.Monad m) => Control.Monad.Fail.MonadFail (Control.Monad.Trans.Free.Ap.FreeT f m)
instance Control.Monad.Trans.Class.MonadTrans (Control.Monad.Trans.Free.Ap.FreeT f)
instance (GHC.Base.Applicative f, GHC.Base.Applicative m, Control.Monad.IO.Class.MonadIO m) => Control.Monad.IO.Class.MonadIO (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Base.Applicative f, GHC.Base.Applicative m, Control.Monad.Reader.Class.MonadReader r m) => Control.Monad.Reader.Class.MonadReader r (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Base.Applicative f, GHC.Base.Applicative m, Control.Monad.Writer.Class.MonadWriter w m) => Control.Monad.Writer.Class.MonadWriter w (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Base.Applicative f, GHC.Base.Applicative m, Control.Monad.State.Class.MonadState s m) => Control.Monad.State.Class.MonadState s (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Base.Applicative f, GHC.Base.Applicative m, Control.Monad.Error.Class.MonadError e m) => Control.Monad.Error.Class.MonadError e (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Base.Applicative f, GHC.Base.Applicative m, Control.Monad.Cont.Class.MonadCont m) => Control.Monad.Cont.Class.MonadCont (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Base.Applicative f, GHC.Base.Applicative m, GHC.Base.MonadPlus m) => GHC.Base.Alternative (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Base.Applicative f, GHC.Base.Applicative m, GHC.Base.MonadPlus m) => GHC.Base.MonadPlus (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Base.Applicative f, GHC.Base.Applicative m, GHC.Base.Monad m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Base.Applicative f, GHC.Base.Applicative m, Control.Monad.Catch.MonadThrow m) => Control.Monad.Catch.MonadThrow (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Base.Applicative f, GHC.Base.Applicative m, Control.Monad.Catch.MonadCatch m) => Control.Monad.Catch.MonadCatch (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (Data.Foldable.Foldable m, Data.Foldable.Foldable f) => Data.Foldable.Foldable (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Base.Monad m, Data.Traversable.Traversable m, Data.Traversable.Traversable f) => Data.Traversable.Traversable (Control.Monad.Trans.Free.Ap.FreeT f m)
instance Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show2 (Control.Monad.Trans.Free.Ap.FreeF f)
instance (Data.Functor.Classes.Show1 f, GHC.Show.Show a) => Data.Functor.Classes.Show1 (Control.Monad.Trans.Free.Ap.FreeF f a)
instance Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read2 (Control.Monad.Trans.Free.Ap.FreeF f)
instance (Data.Functor.Classes.Read1 f, GHC.Read.Read a) => Data.Functor.Classes.Read1 (Control.Monad.Trans.Free.Ap.FreeF f a)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq2 (Control.Monad.Trans.Free.Ap.FreeF f)
instance (Data.Functor.Classes.Eq1 f, GHC.Classes.Eq a) => Data.Functor.Classes.Eq1 (Control.Monad.Trans.Free.Ap.FreeF f a)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord2 (Control.Monad.Trans.Free.Ap.FreeF f)
instance (Data.Functor.Classes.Ord1 f, GHC.Classes.Ord a) => Data.Functor.Classes.Ord1 (Control.Monad.Trans.Free.Ap.FreeF f a)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Monad.Trans.Free.Ap.FreeF f a)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Monad.Trans.Free.Ap.FreeF f a)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Monad.Trans.Free.Ap.FreeF f a)
instance GHC.Base.Functor f => Data.Bifunctor.Bifunctor (Control.Monad.Trans.Free.Ap.FreeF f)
instance Data.Foldable.Foldable f => Data.Bifoldable.Bifoldable (Control.Monad.Trans.Free.Ap.FreeF f)
instance Data.Traversable.Traversable f => Data.Bitraversable.Bitraversable (Control.Monad.Trans.Free.Ap.FreeF f)
-- | The free monad transformer
module Control.Monad.Trans.Free
-- | The base functor for a free monad.
data FreeF f a b
Pure :: a -> FreeF f a b
Free :: (f b) -> FreeF f a b
-- | The "free monad transformer" for a functor f
newtype FreeT f m a
FreeT :: m (FreeF f a (FreeT f m a)) -> FreeT f m a
[runFreeT] :: FreeT f m a -> m (FreeF f a (FreeT f m a))
-- | The "free monad" for a functor f.
type Free f = FreeT f Identity
-- | Pushes a layer into a free monad value.
free :: FreeF f a (Free f a) -> Free f a
-- | Evaluates the first layer out of a free monad value.
runFree :: Free f a -> FreeF f a (Free f a)
-- | A version of lift that can be used with just a Functor for f.
liftF :: (Functor f, MonadFree f m) => f a -> m a
-- | Tear down a free monad transformer using iteration.
iterT :: (Functor f, Monad m) => (f (m a) -> m a) -> FreeT f m a -> m a
-- | Tear down a free monad transformer using iteration over a transformer.
iterTM :: (Functor f, Monad m, MonadTrans t, Monad (t m)) => (f (t m a) -> t m a) -> FreeT f m a -> t m a
-- | Lift a monad homomorphism from m to n into a monad
-- homomorphism from FreeT f m to FreeT f
-- n
--
--
-- hoistFreeT :: (Monad m, Functor f) => (m ~> n) -> FreeT f m ~> FreeT f n
--
hoistFreeT :: (Monad m, Functor f) => (forall a. m a -> n a) -> FreeT f m b -> FreeT f n b
-- | The very definition of a free monad transformer is that given a
-- natural transformation you get a monad transformer homomorphism.
foldFreeT :: (MonadTrans t, Monad (t m), Monad m) => (forall n x. Monad n => f x -> t n x) -> FreeT f m a -> t m a
-- | Lift a natural transformation from f to g into a
-- monad homomorphism from FreeT f m to FreeT
-- g m
transFreeT :: (Monad m, Functor g) => (forall a. f a -> g a) -> FreeT f m b -> FreeT g m b
-- | Pull out and join m layers of FreeT f m a.
joinFreeT :: (Monad m, Traversable f) => FreeT f m a -> m (Free f a)
-- | Cuts off a tree of computations at a given depth. If the depth is
-- 0 or less, no computation nor monadic effects will take
-- place.
--
-- Some examples (n ≥ 0):
--
--
-- cutoff 0 _ ≡ return Nothing
-- cutoff (n+1) . return ≡ return . Just
-- cutoff (n+1) . lift ≡ lift . liftM Just
-- cutoff (n+1) . wrap ≡ wrap . fmap (cutoff n)
--
--
-- Calling retract . cutoff n is always
-- terminating, provided each of the steps in the iteration is
-- terminating.
cutoff :: (Functor f, Monad m) => Integer -> FreeT f m a -> FreeT f m (Maybe a)
-- | partialIterT n phi m interprets first n layers of
-- m using phi. This is sort of the opposite for
-- cutoff.
--
-- Some examples (n ≥ 0):
--
--
-- partialIterT 0 _ m ≡ m
-- partialIterT (n+1) phi . return ≡ return
-- partialIterT (n+1) phi . lift ≡ lift
-- partialIterT (n+1) phi . wrap ≡ join . lift . phi
--
partialIterT :: Monad m => Integer -> (forall a. f a -> m a) -> FreeT f m b -> FreeT f m b
-- | intersperseT f m inserts a layer f between every two
-- layers in m.
--
--
-- intersperseT f . return ≡ return
-- intersperseT f . lift ≡ lift
-- intersperseT f . wrap ≡ wrap . fmap (iterTM (wrap . (<$ f) . wrap))
--
intersperseT :: (Monad m, Functor f) => f a -> FreeT f m b -> FreeT f m b
-- | intercalateT f m inserts a layer f between every two
-- layers in m and then retracts the result.
--
--
-- intercalateT f ≡ retractT . intersperseT f
--
intercalateT :: (Monad m, MonadTrans t, Monad (t m)) => t m a -> FreeT (t m) m b -> t m b
-- | Tear down a free monad transformer using Monad instance for t
-- m.
retractT :: (MonadTrans t, Monad (t m), Monad m) => FreeT (t m) m a -> t m a
-- | retract is the left inverse of liftF
--
--
-- retract . liftF = id
--
retract :: Monad f => Free f a -> f a
-- | Tear down a Free Monad using iteration.
iter :: Functor f => (f a -> a) -> Free f a -> a
-- | Like iter for monadic values.
iterM :: (Functor f, Monad m) => (f (m a) -> m a) -> Free f a -> m a
-- | Monads provide substitution (fmap) and renormalization
-- (join):
--
--
-- m >>= f = join (fmap f m)
--
--
-- A free Monad is one that does no work during the normalization
-- step beyond simply grafting the two monadic values together.
--
-- [] is not a free Monad (in this sense) because
-- join [[a]] smashes the lists flat.
--
-- On the other hand, consider:
--
--
-- data Tree a = Bin (Tree a) (Tree a) | Tip a
--
--
--
-- instance Monad Tree where
-- return = Tip
-- Tip a >>= f = f a
-- Bin l r >>= f = Bin (l >>= f) (r >>= f)
--
--
-- This Monad is the free Monad of Pair:
--
--
-- data Pair a = Pair a a
--
--
-- And we could make an instance of MonadFree for it directly:
--
--
-- instance MonadFree Pair Tree where
-- wrap (Pair l r) = Bin l r
--
--
-- Or we could choose to program with Free Pair instead
-- of Tree and thereby avoid having to define our own
-- Monad instance.
--
-- Moreover, Control.Monad.Free.Church provides a MonadFree
-- instance that can improve the asymptotic complexity of code
-- that constructs free monads by effectively reassociating the use of
-- (>>=). You may also want to take a look at the
-- kan-extensions package
-- (http://hackage.haskell.org/package/kan-extensions).
--
-- See Free for a more formal definition of the free Monad
-- for a Functor.
class Monad m => MonadFree f m | m -> f
-- | Add a layer.
--
--
-- wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--
wrap :: MonadFree f m => f (m a) -> m a
-- | Add a layer.
--
--
-- wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--
wrap :: (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a
instance (GHC.Read.Read (f b), GHC.Read.Read a) => GHC.Read.Read (Control.Monad.Trans.Free.FreeF f a b)
instance (GHC.Show.Show (f b), GHC.Show.Show a) => GHC.Show.Show (Control.Monad.Trans.Free.FreeF f a b)
instance (GHC.Classes.Ord (f b), GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Trans.Free.FreeF f a b)
instance (GHC.Classes.Eq (f b), GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Trans.Free.FreeF f a b)
instance (Data.Functor.Classes.Eq1 f, Data.Functor.Classes.Eq1 m, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Trans.Free.FreeT f m a)
instance (Data.Functor.Classes.Eq1 f, Data.Functor.Classes.Eq1 m) => Data.Functor.Classes.Eq1 (Control.Monad.Trans.Free.FreeT f m)
instance (Data.Functor.Classes.Ord1 f, Data.Functor.Classes.Ord1 m, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Trans.Free.FreeT f m a)
instance (Data.Functor.Classes.Ord1 f, Data.Functor.Classes.Ord1 m) => Data.Functor.Classes.Ord1 (Control.Monad.Trans.Free.FreeT f m)
instance (Data.Functor.Classes.Show1 f, Data.Functor.Classes.Show1 m) => Data.Functor.Classes.Show1 (Control.Monad.Trans.Free.FreeT f m)
instance (Data.Functor.Classes.Show1 f, Data.Functor.Classes.Show1 m, GHC.Show.Show a) => GHC.Show.Show (Control.Monad.Trans.Free.FreeT f m a)
instance (Data.Functor.Classes.Read1 f, Data.Functor.Classes.Read1 m) => Data.Functor.Classes.Read1 (Control.Monad.Trans.Free.FreeT f m)
instance (Data.Functor.Classes.Read1 f, Data.Functor.Classes.Read1 m, GHC.Read.Read a) => GHC.Read.Read (Control.Monad.Trans.Free.FreeT f m a)
instance (GHC.Base.Functor f, GHC.Base.Monad m) => GHC.Base.Functor (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.Monad m) => GHC.Base.Applicative (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.Monad m) => Data.Functor.Bind.Class.Apply (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.Monad m) => Data.Functor.Bind.Class.Bind (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.Monad m) => GHC.Base.Monad (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.Monad m) => Control.Monad.Fail.MonadFail (Control.Monad.Trans.Free.FreeT f m)
instance Control.Monad.Trans.Class.MonadTrans (Control.Monad.Trans.Free.FreeT f)
instance (GHC.Base.Functor f, Control.Monad.IO.Class.MonadIO m) => Control.Monad.IO.Class.MonadIO (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, Control.Monad.Base.MonadBase b m) => Control.Monad.Base.MonadBase b (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, Control.Monad.Reader.Class.MonadReader r m) => Control.Monad.Reader.Class.MonadReader r (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, Control.Monad.Writer.Class.MonadWriter w m) => Control.Monad.Writer.Class.MonadWriter w (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, Control.Monad.State.Class.MonadState s m) => Control.Monad.State.Class.MonadState s (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, Control.Monad.Error.Class.MonadError e m) => Control.Monad.Error.Class.MonadError e (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, Control.Monad.Cont.Class.MonadCont m) => Control.Monad.Cont.Class.MonadCont (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.MonadPlus m) => GHC.Base.Alternative (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.MonadPlus m) => GHC.Base.MonadPlus (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.Monad m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, Control.Monad.Catch.MonadThrow m) => Control.Monad.Catch.MonadThrow (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, Control.Monad.Catch.MonadCatch m) => Control.Monad.Catch.MonadCatch (Control.Monad.Trans.Free.FreeT f m)
instance (Data.Foldable.Foldable m, Data.Foldable.Foldable f) => Data.Foldable.Foldable (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Monad m, Data.Traversable.Traversable m, Data.Traversable.Traversable f) => Data.Traversable.Traversable (Control.Monad.Trans.Free.FreeT f m)
instance Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show2 (Control.Monad.Trans.Free.FreeF f)
instance (Data.Functor.Classes.Show1 f, GHC.Show.Show a) => Data.Functor.Classes.Show1 (Control.Monad.Trans.Free.FreeF f a)
instance Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read2 (Control.Monad.Trans.Free.FreeF f)
instance (Data.Functor.Classes.Read1 f, GHC.Read.Read a) => Data.Functor.Classes.Read1 (Control.Monad.Trans.Free.FreeF f a)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq2 (Control.Monad.Trans.Free.FreeF f)
instance (Data.Functor.Classes.Eq1 f, GHC.Classes.Eq a) => Data.Functor.Classes.Eq1 (Control.Monad.Trans.Free.FreeF f a)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord2 (Control.Monad.Trans.Free.FreeF f)
instance (Data.Functor.Classes.Ord1 f, GHC.Classes.Ord a) => Data.Functor.Classes.Ord1 (Control.Monad.Trans.Free.FreeF f a)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Monad.Trans.Free.FreeF f a)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Monad.Trans.Free.FreeF f a)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Monad.Trans.Free.FreeF f a)
instance GHC.Base.Functor f => Data.Bifunctor.Bifunctor (Control.Monad.Trans.Free.FreeF f)
instance Data.Foldable.Foldable f => Data.Bifoldable.Bifoldable (Control.Monad.Trans.Free.FreeF f)
instance Data.Traversable.Traversable f => Data.Bitraversable.Bitraversable (Control.Monad.Trans.Free.FreeF f)
-- | Church-encoded free monad transformer.
module Control.Monad.Trans.Free.Church
-- | The "free monad transformer" for a functor f
newtype FT f m a
FT :: (forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r) -> FT f m a
[runFT] :: FT f m a -> forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
-- | The "free monad" for a functor f.
type F f = FT f Identity
-- | Wrap a Church-encoding of a "free monad" as the free monad for a
-- functor.
free :: (forall r. (a -> r) -> (f r -> r) -> r) -> F f a
-- | Unwrap the Free monad to obtain it's Church-encoded
-- representation.
runF :: Functor f => F f a -> (forall r. (a -> r) -> (f r -> r) -> r)
-- | Improve the asymptotic performance of code that builds a free monad
-- transformer with only binds and returns by using FT behind the
-- scenes.
--
-- Similar to improve.
improveT :: (Functor f, Monad m) => (forall t. MonadFree f (t m) => t m a) -> FreeT f m a
-- | Generate a Church-encoded free monad transformer from a FreeT
-- monad transformer.
toFT :: Monad m => FreeT f m a -> FT f m a
-- | Convert to a FreeT free monad representation.
fromFT :: (Monad m, Functor f) => FT f m a -> FreeT f m a
-- | Tear down a free monad transformer using iteration.
iterT :: (Functor f, Monad m) => (f (m a) -> m a) -> FT f m a -> m a
-- | Tear down a free monad transformer using iteration over a transformer.
iterTM :: (Functor f, Monad m, MonadTrans t, Monad (t m)) => (f (t m a) -> t m a) -> FT f m a -> t m a
-- | Lift a monad homomorphism from m to n into a monad
-- homomorphism from FT f m to FT f n
--
--
-- hoistFT :: (Monad m, Monad n, Functor f) => (m ~> n) -> FT f m ~> FT f n
--
hoistFT :: (Monad m, Monad n) => (forall a. m a -> n a) -> FT f m b -> FT f n b
-- | Lift a natural transformation from f to g into a
-- monad homomorphism from FT f m to FT g
-- n
transFT :: (forall a. f a -> g a) -> FT f m b -> FT g m b
-- | Pull out and join m layers of FreeT f m a.
joinFT :: (Monad m, Traversable f) => FT f m a -> m (F f a)
-- | Cuts off a tree of computations at a given depth. If the depth is 0 or
-- less, no computation nor monadic effects will take place.
--
-- Some examples (n ≥ 0):
--
--
-- cutoff 0 _ == return Nothing
--
--
--
-- cutoff (n+1) . return == return . Just
--
--
--
-- cutoff (n+1) . lift == lift . liftM Just
--
--
--
-- cutoff (n+1) . wrap == wrap . fmap (cutoff n)
--
--
-- Calling 'retract . cutoff n' is always terminating, provided each of
-- the steps in the iteration is terminating.
cutoff :: (Functor f, Monad m) => Integer -> FT f m a -> FT f m (Maybe a)
-- | Improve the asymptotic performance of code that builds a free monad
-- with only binds and returns by using F behind the scenes.
--
-- This is based on the "Free Monads for Less" series of articles by
-- Edward Kmett:
--
-- http://comonad.com/reader/2011/free-monads-for-less/
-- http://comonad.com/reader/2011/free-monads-for-less-2/
--
-- and "Asymptotic Improvement of Computations over Free Monads" by Janis
-- Voightländer:
--
-- http://www.iai.uni-bonn.de/~jv/mpc08.pdf
improve :: Functor f => (forall m. MonadFree f m => m a) -> Free f a
-- | Convert to another free monad representation.
fromF :: (Functor f, MonadFree f m) => F f a -> m a
-- | Generate a Church-encoded free monad from a Free monad.
toF :: Free f a -> F f a
-- | retract is the left inverse of liftF
--
--
-- retract . liftF = id
--
retract :: Monad f => F f a -> f a
-- | Tear down a free monad transformer using iteration over a transformer.
retractT :: (MonadTrans t, Monad (t m), Monad m) => FT (t m) m a -> t m a
-- | Tear down an F Monad using iteration.
iter :: Functor f => (f a -> a) -> F f a -> a
-- | Like iter for monadic values.
iterM :: (Functor f, Monad m) => (f (m a) -> m a) -> F f a -> m a
-- | Monads provide substitution (fmap) and renormalization
-- (join):
--
--
-- m >>= f = join (fmap f m)
--
--
-- A free Monad is one that does no work during the normalization
-- step beyond simply grafting the two monadic values together.
--
-- [] is not a free Monad (in this sense) because
-- join [[a]] smashes the lists flat.
--
-- On the other hand, consider:
--
--
-- data Tree a = Bin (Tree a) (Tree a) | Tip a
--
--
--
-- instance Monad Tree where
-- return = Tip
-- Tip a >>= f = f a
-- Bin l r >>= f = Bin (l >>= f) (r >>= f)
--
--
-- This Monad is the free Monad of Pair:
--
--
-- data Pair a = Pair a a
--
--
-- And we could make an instance of MonadFree for it directly:
--
--
-- instance MonadFree Pair Tree where
-- wrap (Pair l r) = Bin l r
--
--
-- Or we could choose to program with Free Pair instead
-- of Tree and thereby avoid having to define our own
-- Monad instance.
--
-- Moreover, Control.Monad.Free.Church provides a MonadFree
-- instance that can improve the asymptotic complexity of code
-- that constructs free monads by effectively reassociating the use of
-- (>>=). You may also want to take a look at the
-- kan-extensions package
-- (http://hackage.haskell.org/package/kan-extensions).
--
-- See Free for a more formal definition of the free Monad
-- for a Functor.
class Monad m => MonadFree f m | m -> f
-- | Add a layer.
--
--
-- wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--
wrap :: MonadFree f m => f (m a) -> m a
-- | Add a layer.
--
--
-- wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--
wrap :: (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a
-- | A version of lift that can be used with just a Functor for f.
liftF :: (Functor f, MonadFree f m) => f a -> m a
instance (GHC.Base.Functor f, GHC.Base.Monad m, Data.Functor.Classes.Eq1 f, Data.Functor.Classes.Eq1 m) => Data.Functor.Classes.Eq1 (Control.Monad.Trans.Free.Church.FT f m)
instance (GHC.Base.Functor f, GHC.Base.Monad m, Data.Functor.Classes.Ord1 f, Data.Functor.Classes.Ord1 m) => Data.Functor.Classes.Ord1 (Control.Monad.Trans.Free.Church.FT f m)
instance (Data.Functor.Classes.Eq1 (Control.Monad.Trans.Free.Church.FT f m), GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Trans.Free.Church.FT f m a)
instance (Data.Functor.Classes.Ord1 (Control.Monad.Trans.Free.Church.FT f m), GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Trans.Free.Church.FT f m a)
instance GHC.Base.Functor (Control.Monad.Trans.Free.Church.FT f m)
instance Data.Functor.Bind.Class.Apply (Control.Monad.Trans.Free.Church.FT f m)
instance GHC.Base.Applicative (Control.Monad.Trans.Free.Church.FT f m)
instance Data.Functor.Bind.Class.Bind (Control.Monad.Trans.Free.Church.FT f m)
instance GHC.Base.Monad (Control.Monad.Trans.Free.Church.FT f m)
instance Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Free.Church.FT f m)
instance Control.Monad.Trans.Class.MonadTrans (Control.Monad.Trans.Free.Church.FT f)
instance GHC.Base.Alternative m => GHC.Base.Alternative (Control.Monad.Trans.Free.Church.FT f m)
instance GHC.Base.MonadPlus m => GHC.Base.MonadPlus (Control.Monad.Trans.Free.Church.FT f m)
instance (Data.Foldable.Foldable f, Data.Foldable.Foldable m, GHC.Base.Monad m) => Data.Foldable.Foldable (Control.Monad.Trans.Free.Church.FT f m)
instance (GHC.Base.Monad m, Data.Traversable.Traversable m, Data.Traversable.Traversable f) => Data.Traversable.Traversable (Control.Monad.Trans.Free.Church.FT f m)
instance Control.Monad.IO.Class.MonadIO m => Control.Monad.IO.Class.MonadIO (Control.Monad.Trans.Free.Church.FT f m)
instance (GHC.Base.Functor f, Control.Monad.Error.Class.MonadError e m) => Control.Monad.Error.Class.MonadError e (Control.Monad.Trans.Free.Church.FT f m)
instance Control.Monad.Cont.Class.MonadCont m => Control.Monad.Cont.Class.MonadCont (Control.Monad.Trans.Free.Church.FT f m)
instance Control.Monad.Reader.Class.MonadReader r m => Control.Monad.Reader.Class.MonadReader r (Control.Monad.Trans.Free.Church.FT f m)
instance (GHC.Base.Functor f, Control.Monad.Writer.Class.MonadWriter w m) => Control.Monad.Writer.Class.MonadWriter w (Control.Monad.Trans.Free.Church.FT f m)
instance Control.Monad.State.Class.MonadState s m => Control.Monad.State.Class.MonadState s (Control.Monad.Trans.Free.Church.FT f m)
instance Control.Monad.Catch.MonadThrow m => Control.Monad.Catch.MonadThrow (Control.Monad.Trans.Free.Church.FT f m)
instance (GHC.Base.Functor f, Control.Monad.Catch.MonadCatch m) => Control.Monad.Catch.MonadCatch (Control.Monad.Trans.Free.Church.FT f m)
-- | "Applicative Effects in Free Monads"
--
-- Often times, the '(*)' operator can be more efficient than
-- ap. Conventional free monads don't provide any means of
-- modeling this. The free monad can be modified to make use of an
-- underlying applicative. But it does require some laws, or else the
-- '(*)' = ap law is broken. When interpreting this free
-- monad with foldFree, the natural transformation must be an
-- applicative homomorphism. An applicative homomorphism hm ::
-- (Applicative f, Applicative g) => f x -> g x will satisfy
-- these laws.
--
--
-- hm (pure a) = pure a
hm (f * a) = hm f * hm a
--
-- This is based on the "Applicative Effects in Free Monads" series of
-- articles by Will Fancher
--
--
module Control.Monad.Free.Ap
-- | Monads provide substitution (fmap) and renormalization
-- (join):
--
--
-- m >>= f = join (fmap f m)
--
--
-- A free Monad is one that does no work during the normalization
-- step beyond simply grafting the two monadic values together.
--
-- [] is not a free Monad (in this sense) because
-- join [[a]] smashes the lists flat.
--
-- On the other hand, consider:
--
--
-- data Tree a = Bin (Tree a) (Tree a) | Tip a
--
--
--
-- instance Monad Tree where
-- return = Tip
-- Tip a >>= f = f a
-- Bin l r >>= f = Bin (l >>= f) (r >>= f)
--
--
-- This Monad is the free Monad of Pair:
--
--
-- data Pair a = Pair a a
--
--
-- And we could make an instance of MonadFree for it directly:
--
--
-- instance MonadFree Pair Tree where
-- wrap (Pair l r) = Bin l r
--
--
-- Or we could choose to program with Free Pair instead
-- of Tree and thereby avoid having to define our own
-- Monad instance.
--
-- Moreover, Control.Monad.Free.Church provides a MonadFree
-- instance that can improve the asymptotic complexity of code
-- that constructs free monads by effectively reassociating the use of
-- (>>=). You may also want to take a look at the
-- kan-extensions package
-- (http://hackage.haskell.org/package/kan-extensions).
--
-- See Free for a more formal definition of the free Monad
-- for a Functor.
class Monad m => MonadFree f m | m -> f
-- | Add a layer.
--
--
-- wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--
wrap :: MonadFree f m => f (m a) -> m a
-- | Add a layer.
--
--
-- wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--
wrap :: (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a
-- | A free monad given an applicative
data Free f a
Pure :: a -> Free f a
Free :: (f (Free f a)) -> Free f a
-- | retract is the left inverse of lift and liftF
--
--
-- retract . lift = id
-- retract . liftF = id
--
retract :: (Applicative f, Monad f) => Free f a -> f a
-- | A version of lift that can be used with just a Functor for f.
liftF :: (Functor f, MonadFree f m) => f a -> m a
-- | Given an applicative homomorphism from f to
-- Identity, tear down a Free Monad using
-- iteration.
iter :: Applicative f => (f a -> a) -> Free f a -> a
-- | Like iter for applicative values.
iterA :: (Applicative p, Applicative f) => (f (p a) -> p a) -> Free f a -> p a
-- | Like iter for monadic values.
iterM :: (Applicative m, Monad m, Applicative f) => (f (m a) -> m a) -> Free f a -> m a
-- | Lift an applicative homomorphism from f to g into a
-- monad homomorphism from Free f to Free
-- g.
hoistFree :: (Applicative f, Applicative g) => (forall a. f a -> g a) -> Free f b -> Free g b
-- | Given an applicative homomorphism, you get a monad homomorphism.
foldFree :: (Applicative f, Applicative m, Monad m) => (forall x. f x -> m x) -> Free f a -> m a
-- | Convert a Free monad from Control.Monad.Free.Ap to a
-- FreeT monad from Control.Monad.Trans.Free.Ap. WARNING:
-- This assumes that liftF is an applicative homomorphism.
toFreeT :: (Applicative f, Applicative m, Monad m) => Free f a -> FreeT f m a
-- | Cuts off a tree of computations at a given depth. If the depth is 0 or
-- less, no computation nor monadic effects will take place.
--
-- Some examples (n ≥ 0):
--
--
-- cutoff 0 _ == return Nothing
--
--
--
-- cutoff (n+1) . return == return . Just
--
--
--
-- cutoff (n+1) . lift == lift . liftM Just
--
--
--
-- cutoff (n+1) . wrap == wrap . fmap (cutoff n)
--
--
-- Calling 'retract . cutoff n' is always terminating, provided each of
-- the steps in the iteration is terminating.
cutoff :: (Applicative f) => Integer -> Free f a -> Free f (Maybe a)
-- | Unfold a free monad from a seed.
unfold :: Applicative f => (b -> Either a (f b)) -> b -> Free f a
-- | Unfold a free monad from a seed, monadically.
unfoldM :: (Applicative f, Traversable f, Applicative m, Monad m) => (b -> m (Either a (f b))) -> b -> m (Free f a)
-- | This is Prism' (Free f a) a in disguise
--
--
-- >>> preview _Pure (Pure 3)
-- Just 3
--
--
--
-- >>> review _Pure 3 :: Free Maybe Int
-- Pure 3
--
_Pure :: forall f m a p. (Choice p, Applicative m) => p a (m a) -> p (Free f a) (m (Free f a))
-- | This is Prism' (Free f a) (f (Free f a)) in disguise
--
--
-- >>> preview _Free (review _Free (Just (Pure 3)))
-- Just (Just (Pure 3))
--
--
--
-- >>> review _Free (Just (Pure 3))
-- Free (Just (Pure 3))
--
_Free :: forall f m a p. (Choice p, Applicative m) => p (f (Free f a)) (m (f (Free f a))) -> p (Free f a) (m (Free f a))
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq1 (Control.Monad.Free.Ap.Free f)
instance (Data.Functor.Classes.Eq1 f, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Free.Ap.Free f a)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord1 (Control.Monad.Free.Ap.Free f)
instance (Data.Functor.Classes.Ord1 f, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Free.Ap.Free f a)
instance Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show1 (Control.Monad.Free.Ap.Free f)
instance (Data.Functor.Classes.Show1 f, GHC.Show.Show a) => GHC.Show.Show (Control.Monad.Free.Ap.Free f a)
instance Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read1 (Control.Monad.Free.Ap.Free f)
instance (Data.Functor.Classes.Read1 f, GHC.Read.Read a) => GHC.Read.Read (Control.Monad.Free.Ap.Free f a)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Monad.Free.Ap.Free f)
instance Data.Functor.Bind.Class.Apply f => Data.Functor.Bind.Class.Apply (Control.Monad.Free.Ap.Free f)
instance GHC.Base.Applicative f => GHC.Base.Applicative (Control.Monad.Free.Ap.Free f)
instance Data.Functor.Bind.Class.Apply f => Data.Functor.Bind.Class.Bind (Control.Monad.Free.Ap.Free f)
instance GHC.Base.Applicative f => GHC.Base.Monad (Control.Monad.Free.Ap.Free f)
instance GHC.Base.Applicative f => Control.Monad.Fix.MonadFix (Control.Monad.Free.Ap.Free f)
instance GHC.Base.Alternative v => GHC.Base.Alternative (Control.Monad.Free.Ap.Free v)
instance (GHC.Base.Applicative v, GHC.Base.MonadPlus v) => GHC.Base.MonadPlus (Control.Monad.Free.Ap.Free v)
instance Control.Monad.Trans.Class.MonadTrans Control.Monad.Free.Ap.Free
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Monad.Free.Ap.Free f)
instance Data.Semigroup.Foldable.Class.Foldable1 f => Data.Semigroup.Foldable.Class.Foldable1 (Control.Monad.Free.Ap.Free f)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Monad.Free.Ap.Free f)
instance Data.Semigroup.Traversable.Class.Traversable1 f => Data.Semigroup.Traversable.Class.Traversable1 (Control.Monad.Free.Ap.Free f)
instance (GHC.Base.Applicative m, Control.Monad.Writer.Class.MonadWriter e m) => Control.Monad.Writer.Class.MonadWriter e (Control.Monad.Free.Ap.Free m)
instance (GHC.Base.Applicative m, Control.Monad.Reader.Class.MonadReader e m) => Control.Monad.Reader.Class.MonadReader e (Control.Monad.Free.Ap.Free m)
instance (GHC.Base.Applicative m, Control.Monad.State.Class.MonadState s m) => Control.Monad.State.Class.MonadState s (Control.Monad.Free.Ap.Free m)
instance (GHC.Base.Applicative m, Control.Monad.Error.Class.MonadError e m) => Control.Monad.Error.Class.MonadError e (Control.Monad.Free.Ap.Free m)
instance (GHC.Base.Applicative m, Control.Monad.Cont.Class.MonadCont m) => Control.Monad.Cont.Class.MonadCont (Control.Monad.Free.Ap.Free m)
instance GHC.Base.Applicative f => Control.Monad.Free.Class.MonadFree f (Control.Monad.Free.Ap.Free f)
-- | Monads for free
module Control.Monad.Free
-- | Monads provide substitution (fmap) and renormalization
-- (join):
--
--
-- m >>= f = join (fmap f m)
--
--
-- A free Monad is one that does no work during the normalization
-- step beyond simply grafting the two monadic values together.
--
-- [] is not a free Monad (in this sense) because
-- join [[a]] smashes the lists flat.
--
-- On the other hand, consider:
--
--
-- data Tree a = Bin (Tree a) (Tree a) | Tip a
--
--
--
-- instance Monad Tree where
-- return = Tip
-- Tip a >>= f = f a
-- Bin l r >>= f = Bin (l >>= f) (r >>= f)
--
--
-- This Monad is the free Monad of Pair:
--
--
-- data Pair a = Pair a a
--
--
-- And we could make an instance of MonadFree for it directly:
--
--
-- instance MonadFree Pair Tree where
-- wrap (Pair l r) = Bin l r
--
--
-- Or we could choose to program with Free Pair instead
-- of Tree and thereby avoid having to define our own
-- Monad instance.
--
-- Moreover, Control.Monad.Free.Church provides a MonadFree
-- instance that can improve the asymptotic complexity of code
-- that constructs free monads by effectively reassociating the use of
-- (>>=). You may also want to take a look at the
-- kan-extensions package
-- (http://hackage.haskell.org/package/kan-extensions).
--
-- See Free for a more formal definition of the free Monad
-- for a Functor.
class Monad m => MonadFree f m | m -> f
-- | Add a layer.
--
--
-- wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--
wrap :: MonadFree f m => f (m a) -> m a
-- | Add a layer.
--
--
-- wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--
wrap :: (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a
-- | The Free Monad for a Functor f.
--
-- Formally
--
-- A Monad n is a free Monad for f if
-- every monad homomorphism from n to another monad m
-- is equivalent to a natural transformation from f to
-- m.
--
-- Why Free?
--
-- Every "free" functor is left adjoint to some "forgetful" functor.
--
-- If we define a forgetful functor U from the category of
-- monads to the category of functors that just forgets the Monad,
-- leaving only the Functor. i.e.
--
--
-- U (M,return,join) = M
--
--
-- then Free is the left adjoint to U.
--
-- Being Free being left adjoint to U means that there is
-- an isomorphism between
--
-- Free f -> m in the category of monads and f
-- -> U m in the category of functors.
--
-- Morphisms in the category of monads are Monad homomorphisms
-- (natural transformations that respect return and join).
--
-- Morphisms in the category of functors are Functor homomorphisms
-- (natural transformations).
--
-- Given this isomorphism, every monad homomorphism from Free
-- f to m is equivalent to a natural transformation from
-- f to m
--
-- Showing that this isomorphism holds is left as an exercise.
--
-- In practice, you can just view a Free f a as many
-- layers of f wrapped around values of type a, where
-- (>>=) performs substitution and grafts new
-- layers of f in for each of the free variables.
--
-- This can be very useful for modeling domain specific languages, trees,
-- or other constructs.
--
-- This instance of MonadFree is fairly naive about the encoding.
-- For more efficient free monad implementation see
-- Control.Monad.Free.Church, in particular note the
-- improve combinator. You may also want to take a look at the
-- kan-extensions package
-- (http://hackage.haskell.org/package/kan-extensions).
--
-- A number of common monads arise as free monads,
--
--
-- - Given data Empty a, Free Empty is
-- isomorphic to the Identity monad.
-- - Free Maybe can be used to model a
-- partiality monad where each layer represents running the computation
-- for a while longer.
--
data Free f a
Pure :: a -> Free f a
Free :: (f (Free f a)) -> Free f a
-- | retract is the left inverse of lift and liftF
--
--
-- retract . lift = id
-- retract . liftF = id
--
retract :: Monad f => Free f a -> f a
-- | A version of lift that can be used with just a Functor for f.
liftF :: (Functor f, MonadFree f m) => f a -> m a
-- | Tear down a Free Monad using iteration.
iter :: Functor f => (f a -> a) -> Free f a -> a
-- | Like iter for applicative values.
iterA :: (Applicative p, Functor f) => (f (p a) -> p a) -> Free f a -> p a
-- | Like iter for monadic values.
iterM :: (Monad m, Functor f) => (f (m a) -> m a) -> Free f a -> m a
-- | Lift a natural transformation from f to g into a
-- natural transformation from FreeT f to
-- FreeT g.
hoistFree :: Functor g => (forall a. f a -> g a) -> Free f b -> Free g b
-- | The very definition of a free monad is that given a natural
-- transformation you get a monad homomorphism.
foldFree :: Monad m => (forall x. f x -> m x) -> Free f a -> m a
-- | Convert a Free monad from Control.Monad.Free to a
-- FreeT monad from Control.Monad.Trans.Free.
toFreeT :: (Functor f, Monad m) => Free f a -> FreeT f m a
-- | Cuts off a tree of computations at a given depth. If the depth is 0 or
-- less, no computation nor monadic effects will take place.
--
-- Some examples (n ≥ 0):
--
--
-- cutoff 0 _ == return Nothing
--
--
--
-- cutoff (n+1) . return == return . Just
--
--
--
-- cutoff (n+1) . lift == lift . liftM Just
--
--
--
-- cutoff (n+1) . wrap == wrap . fmap (cutoff n)
--
--
-- Calling 'retract . cutoff n' is always terminating, provided each of
-- the steps in the iteration is terminating.
cutoff :: (Functor f) => Integer -> Free f a -> Free f (Maybe a)
-- | Unfold a free monad from a seed.
unfold :: Functor f => (b -> Either a (f b)) -> b -> Free f a
-- | Unfold a free monad from a seed, monadically.
unfoldM :: (Traversable f, Applicative m, Monad m) => (b -> m (Either a (f b))) -> b -> m (Free f a)
-- | This is Prism' (Free f a) a in disguise
--
--
-- >>> preview _Pure (Pure 3)
-- Just 3
--
--
--
-- >>> review _Pure 3 :: Free Maybe Int
-- Pure 3
--
_Pure :: forall f m a p. (Choice p, Applicative m) => p a (m a) -> p (Free f a) (m (Free f a))
-- | This is Prism' (Free f a) (f (Free f a)) in disguise
--
--
-- >>> preview _Free (review _Free (Just (Pure 3)))
-- Just (Just (Pure 3))
--
--
--
-- >>> review _Free (Just (Pure 3))
-- Free (Just (Pure 3))
--
_Free :: forall f m a p. (Choice p, Applicative m) => p (f (Free f a)) (m (f (Free f a))) -> p (Free f a) (m (Free f a))
instance (Data.Typeable.Internal.Typeable f, Data.Data.Data (f (Control.Monad.Free.Free f a)), Data.Data.Data a) => Data.Data.Data (Control.Monad.Free.Free f a)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq1 (Control.Monad.Free.Free f)
instance (Data.Functor.Classes.Eq1 f, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Free.Free f a)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord1 (Control.Monad.Free.Free f)
instance (Data.Functor.Classes.Ord1 f, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Free.Free f a)
instance Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show1 (Control.Monad.Free.Free f)
instance (Data.Functor.Classes.Show1 f, GHC.Show.Show a) => GHC.Show.Show (Control.Monad.Free.Free f a)
instance Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read1 (Control.Monad.Free.Free f)
instance (Data.Functor.Classes.Read1 f, GHC.Read.Read a) => GHC.Read.Read (Control.Monad.Free.Free f a)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Monad.Free.Free f)
instance GHC.Base.Functor f => Data.Functor.Bind.Class.Apply (Control.Monad.Free.Free f)
instance GHC.Base.Functor f => GHC.Base.Applicative (Control.Monad.Free.Free f)
instance GHC.Base.Functor f => Data.Functor.Bind.Class.Bind (Control.Monad.Free.Free f)
instance GHC.Base.Functor f => GHC.Base.Monad (Control.Monad.Free.Free f)
instance GHC.Base.Functor f => Control.Monad.Fix.MonadFix (Control.Monad.Free.Free f)
instance GHC.Base.Alternative v => GHC.Base.Alternative (Control.Monad.Free.Free v)
instance (GHC.Base.Functor v, GHC.Base.MonadPlus v) => GHC.Base.MonadPlus (Control.Monad.Free.Free v)
instance Control.Monad.Trans.Class.MonadTrans Control.Monad.Free.Free
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Monad.Free.Free f)
instance Data.Semigroup.Foldable.Class.Foldable1 f => Data.Semigroup.Foldable.Class.Foldable1 (Control.Monad.Free.Free f)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Monad.Free.Free f)
instance Data.Semigroup.Traversable.Class.Traversable1 f => Data.Semigroup.Traversable.Class.Traversable1 (Control.Monad.Free.Free f)
instance (GHC.Base.Functor m, Control.Monad.Writer.Class.MonadWriter e m) => Control.Monad.Writer.Class.MonadWriter e (Control.Monad.Free.Free m)
instance (GHC.Base.Functor m, Control.Monad.Reader.Class.MonadReader e m) => Control.Monad.Reader.Class.MonadReader e (Control.Monad.Free.Free m)
instance (GHC.Base.Functor m, Control.Monad.State.Class.MonadState s m) => Control.Monad.State.Class.MonadState s (Control.Monad.Free.Free m)
instance (GHC.Base.Functor m, Control.Monad.Error.Class.MonadError e m) => Control.Monad.Error.Class.MonadError e (Control.Monad.Free.Free m)
instance (GHC.Base.Functor m, Control.Monad.Cont.Class.MonadCont m) => Control.Monad.Cont.Class.MonadCont (Control.Monad.Free.Free m)
instance GHC.Base.Functor f => Control.Monad.Free.Class.MonadFree f (Control.Monad.Free.Free f)
-- | "Free Monads for Less"
--
-- The most straightforward way of implementing free monads is as a
-- recursive datatype that allows for arbitrarily deep nesting of the
-- base functor. This is akin to a tree, with the leaves containing the
-- values, and the nodes being a level of Functor over subtrees.
--
-- For each time that the fmap or >>= operations is
-- used, the old tree is traversed up to the leaves, a new set of nodes
-- is allocated, and the old ones are garbage collected. Even if the
-- Haskell runtime optimizes some of the overhead through laziness and
-- generational garbage collection, the asymptotic runtime is still
-- quadratic.
--
-- On the other hand, if the Church encoding is used, the tree only needs
-- to be constructed once, because:
--
--
-- - All uses of fmap are collapsed into a single one, so that
-- the values on the _leaves_ are transformed in one pass.
--
--
--
-- fmap f . fmap g == fmap (f . g)
--
--
--
-- - All uses of >>= are right associated, so that every
-- new subtree created is final.
--
--
--
-- (m >>= f) >>= g == m >>= (\x -> f x >>= g)
--
--
-- Asymptotically, the Church encoding supports the monadic operations
-- more efficiently than the naïve Free.
--
-- This is based on the "Free Monads for Less" series of articles by
-- Edward Kmett:
--
--
module Control.Monad.Free.Church
-- | The Church-encoded free monad for a functor f.
--
-- It is asymptotically more efficient to use (>>=)
-- for F than it is to (>>=) with Free.
--
-- http://comonad.com/reader/2011/free-monads-for-less-2/
newtype F f a
F :: (forall r. (a -> r) -> (f r -> r) -> r) -> F f a
[runF] :: F f a -> forall r. (a -> r) -> (f r -> r) -> r
-- | Improve the asymptotic performance of code that builds a free monad
-- with only binds and returns by using F behind the scenes.
--
-- This is based on the "Free Monads for Less" series of articles by
-- Edward Kmett:
--
--
--
-- and "Asymptotic Improvement of Computations over Free Monads"
-- by Janis Voightländer.
improve :: Functor f => (forall m. MonadFree f m => m a) -> Free f a
-- | Convert to another free monad representation.
fromF :: MonadFree f m => F f a -> m a
-- | Tear down a Free Monad using iteration.
iter :: (f a -> a) -> F f a -> a
-- | Like iter for monadic values.
iterM :: Monad m => (f (m a) -> m a) -> F f a -> m a
-- | Generate a Church-encoded free monad from a Free monad.
toF :: Functor f => Free f a -> F f a
-- | retract is the left inverse of lift and liftF
--
--
-- retract . lift = id
-- retract . liftF = id
--
retract :: Monad m => F m a -> m a
-- | Lift a natural transformation from f to g into a
-- natural transformation from F f to F g.
hoistF :: (forall x. f x -> g x) -> F f a -> F g a
-- | The very definition of a free monad is that given a natural
-- transformation you get a monad homomorphism.
foldF :: Monad m => (forall x. f x -> m x) -> F f a -> m a
-- | Monads provide substitution (fmap) and renormalization
-- (join):
--
--
-- m >>= f = join (fmap f m)
--
--
-- A free Monad is one that does no work during the normalization
-- step beyond simply grafting the two monadic values together.
--
-- [] is not a free Monad (in this sense) because
-- join [[a]] smashes the lists flat.
--
-- On the other hand, consider:
--
--
-- data Tree a = Bin (Tree a) (Tree a) | Tip a
--
--
--
-- instance Monad Tree where
-- return = Tip
-- Tip a >>= f = f a
-- Bin l r >>= f = Bin (l >>= f) (r >>= f)
--
--
-- This Monad is the free Monad of Pair:
--
--
-- data Pair a = Pair a a
--
--
-- And we could make an instance of MonadFree for it directly:
--
--
-- instance MonadFree Pair Tree where
-- wrap (Pair l r) = Bin l r
--
--
-- Or we could choose to program with Free Pair instead
-- of Tree and thereby avoid having to define our own
-- Monad instance.
--
-- Moreover, Control.Monad.Free.Church provides a MonadFree
-- instance that can improve the asymptotic complexity of code
-- that constructs free monads by effectively reassociating the use of
-- (>>=). You may also want to take a look at the
-- kan-extensions package
-- (http://hackage.haskell.org/package/kan-extensions).
--
-- See Free for a more formal definition of the free Monad
-- for a Functor.
class Monad m => MonadFree f m | m -> f
-- | Add a layer.
--
--
-- wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--
wrap :: MonadFree f m => f (m a) -> m a
-- | Add a layer.
--
--
-- wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--
wrap :: (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a
-- | A version of lift that can be used with just a Functor for f.
liftF :: (Functor f, MonadFree f m) => f a -> m a
-- | Cuts off a tree of computations at a given depth. If the depth is 0 or
-- less, no computation nor monadic effects will take place.
--
-- Some examples (n ≥ 0):
--
--
-- cutoff 0 _ == return Nothing
--
--
--
-- cutoff (n+1) . return == return . Just
--
--
--
-- cutoff (n+1) . lift == lift . liftM Just
--
--
--
-- cutoff (n+1) . wrap == wrap . fmap (cutoff n)
--
--
-- Calling retract . cutoff n is always
-- terminating, provided each of the steps in the iteration is
-- terminating.
cutoff :: (Functor f) => Integer -> F f a -> F f (Maybe a)
instance GHC.Base.Functor (Control.Monad.Free.Church.F f)
instance Data.Functor.Bind.Class.Apply (Control.Monad.Free.Church.F f)
instance GHC.Base.Applicative (Control.Monad.Free.Church.F f)
instance GHC.Base.Alternative f => GHC.Base.Alternative (Control.Monad.Free.Church.F f)
instance Data.Functor.Bind.Class.Bind (Control.Monad.Free.Church.F f)
instance GHC.Base.Monad (Control.Monad.Free.Church.F f)
instance Control.Monad.Fix.MonadFix (Control.Monad.Free.Church.F f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Monad.Free.Church.F f)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Monad.Free.Church.F f)
instance Data.Semigroup.Foldable.Class.Foldable1 f => Data.Semigroup.Foldable.Class.Foldable1 (Control.Monad.Free.Church.F f)
instance Data.Semigroup.Traversable.Class.Traversable1 f => Data.Semigroup.Traversable.Class.Traversable1 (Control.Monad.Free.Church.F f)
instance GHC.Base.MonadPlus f => GHC.Base.MonadPlus (Control.Monad.Free.Church.F f)
instance Control.Monad.Trans.Class.MonadTrans Control.Monad.Free.Church.F
instance GHC.Base.Functor f => Control.Monad.Free.Class.MonadFree f (Control.Monad.Free.Church.F f)
instance Control.Monad.State.Class.MonadState s m => Control.Monad.State.Class.MonadState s (Control.Monad.Free.Church.F m)
instance Control.Monad.Reader.Class.MonadReader e m => Control.Monad.Reader.Class.MonadReader e (Control.Monad.Free.Church.F m)
instance Control.Monad.Writer.Class.MonadWriter w m => Control.Monad.Writer.Class.MonadWriter w (Control.Monad.Free.Church.F m)
instance Control.Monad.Cont.Class.MonadCont m => Control.Monad.Cont.Class.MonadCont (Control.Monad.Free.Church.F m)
-- | The coiterative comonad generated by a comonad
module Control.Comonad.Trans.Coiter
-- | This is the coiterative comonad generated by a comonad
newtype CoiterT w a
CoiterT :: w (a, CoiterT w a) -> CoiterT w a
[runCoiterT] :: CoiterT w a -> w (a, CoiterT w a)
-- | The coiterative comonad
type Coiter = CoiterT Identity
-- | Prepends a result to a coiterative computation.
--
--
-- runCoiter . uncurry coiter == id
--
coiter :: a -> Coiter a -> Coiter a
-- | Extracts the first result from a coiterative computation.
--
--
-- uncurry coiter . runCoiter == id
--
runCoiter :: Coiter a -> (a, Coiter a)
-- | Unfold a CoiterT comonad transformer from a cokleisli arrow
-- and an initial comonadic seed.
unfold :: Comonad w => (w a -> a) -> w a -> CoiterT w a
-- | Allows you to peel a layer off a cofree comonad.
class (Functor f, Comonad w) => ComonadCofree f w | w -> f
-- | Remove a layer.
unwrap :: ComonadCofree f w => w a -> f (w a)
instance Data.Functor.Classes.Eq1 w => Data.Functor.Classes.Eq1 (Control.Comonad.Trans.Coiter.CoiterT w)
instance Data.Functor.Classes.Ord1 w => Data.Functor.Classes.Ord1 (Control.Comonad.Trans.Coiter.CoiterT w)
instance Data.Functor.Classes.Show1 w => Data.Functor.Classes.Show1 (Control.Comonad.Trans.Coiter.CoiterT w)
instance Data.Functor.Classes.Read1 w => Data.Functor.Classes.Read1 (Control.Comonad.Trans.Coiter.CoiterT w)
instance GHC.Base.Functor w => GHC.Base.Functor (Control.Comonad.Trans.Coiter.CoiterT w)
instance Control.Comonad.Comonad w => Control.Comonad.Comonad (Control.Comonad.Trans.Coiter.CoiterT w)
instance Data.Foldable.Foldable w => Data.Foldable.Foldable (Control.Comonad.Trans.Coiter.CoiterT w)
instance Data.Traversable.Traversable w => Data.Traversable.Traversable (Control.Comonad.Trans.Coiter.CoiterT w)
instance Control.Comonad.Trans.Class.ComonadTrans Control.Comonad.Trans.Coiter.CoiterT
instance Control.Comonad.Comonad w => Control.Comonad.Cofree.Class.ComonadCofree Data.Functor.Identity.Identity (Control.Comonad.Trans.Coiter.CoiterT w)
instance Control.Comonad.Env.Class.ComonadEnv e w => Control.Comonad.Env.Class.ComonadEnv e (Control.Comonad.Trans.Coiter.CoiterT w)
instance Control.Comonad.Hoist.Class.ComonadHoist Control.Comonad.Trans.Coiter.CoiterT
instance Control.Comonad.Traced.Class.ComonadTraced m w => Control.Comonad.Traced.Class.ComonadTraced m (Control.Comonad.Trans.Coiter.CoiterT w)
instance Control.Comonad.Store.Class.ComonadStore s w => Control.Comonad.Store.Class.ComonadStore s (Control.Comonad.Trans.Coiter.CoiterT w)
instance (Data.Functor.Classes.Show1 w, GHC.Show.Show a) => GHC.Show.Show (Control.Comonad.Trans.Coiter.CoiterT w a)
instance (Data.Functor.Classes.Read1 w, GHC.Read.Read a) => GHC.Read.Read (Control.Comonad.Trans.Coiter.CoiterT w a)
instance (Data.Functor.Classes.Eq1 w, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Comonad.Trans.Coiter.CoiterT w a)
instance (Data.Functor.Classes.Ord1 w, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Comonad.Trans.Coiter.CoiterT w a)
instance (Data.Typeable.Internal.Typeable w, Data.Typeable.Internal.Typeable a, Data.Data.Data (w (a, Control.Comonad.Trans.Coiter.CoiterT w a)), Data.Data.Data a) => Data.Data.Data (Control.Comonad.Trans.Coiter.CoiterT w a)
-- | Cofree comonads
module Control.Comonad.Cofree
-- | The Cofree Comonad of a functor f.
--
-- Formally
--
-- A Comonad v is a cofree Comonad for f
-- if every comonad homomorphism from another comonad w to
-- v is equivalent to a natural transformation from w
-- to f.
--
-- A cofree functor is right adjoint to a forgetful functor.
--
-- Cofree is a functor from the category of functors to the category of
-- comonads that is right adjoint to the forgetful functor from the
-- category of comonads to the category of functors that forgets how to
-- extract and duplicate, leaving you with only a
-- Functor.
--
-- In practice, cofree comonads are quite useful for annotating syntax
-- trees, or talking about streams.
--
-- A number of common comonads arise directly as cofree comonads.
--
-- For instance,
--
--
-- - Cofree Maybe forms the a comonad for a
-- non-empty list.
-- - Cofree (Const b) is a product.
-- - Cofree Identity forms an infinite
-- stream.
-- - Cofree ((->) b)' describes a Moore machine with
-- states labeled with values of type a, and transitions on edges of type
-- b.
--
--
-- Furthermore, if the functor f forms a monoid (for example, by
-- being an instance of Alternative), the resulting Comonad
-- is also a Monad. See Monadic Augment and Generalised
-- Shortcut Fusion by Neil Ghani et al., Section 4.3 for more
-- details.
--
-- In particular, if f a ≡ [a], the resulting data structure is
-- a Rose tree. For a practical application, check Higher
-- Dimensional Trees, Algebraically by Neil Ghani et al.
data Cofree f a
(:<) :: a -> f (Cofree f a) -> Cofree f a
-- | Allows you to peel a layer off a cofree comonad.
class (Functor f, Comonad w) => ComonadCofree f w | w -> f
-- | Remove a layer.
unwrap :: ComonadCofree f w => w a -> f (w a)
-- |
-- lower . section = id
--
section :: Comonad f => f a -> Cofree f a
-- | Use coiteration to generate a cofree comonad from a seed.
--
--
-- coiter f = unfold (id &&& f)
--
coiter :: Functor f => (a -> f a) -> a -> Cofree f a
-- | Like coiter for comonadic values.
coiterW :: (Comonad w, Functor f) => (w a -> f (w a)) -> w a -> Cofree f a
-- | Unfold a cofree comonad from a seed.
unfold :: Functor f => (b -> (a, f b)) -> b -> Cofree f a
-- | Unfold a cofree comonad from a seed, monadically.
unfoldM :: (Traversable f, Monad m) => (b -> m (a, f b)) -> b -> m (Cofree f a)
hoistCofree :: Functor f => (forall x. f x -> g x) -> Cofree f a -> Cofree g a
-- | This is a lens that can be used to read or write from the target of
-- extract.
--
-- Using (^.) from the lens package:
--
--
-- foo ^. _extract == extract foo
--
--
-- For more on lenses see the lens package on hackage
--
--
-- _extract :: Lens' (Cofree g a) a
--
_extract :: Functor f => (a -> f a) -> Cofree g a -> f (Cofree g a)
-- | This is a lens that can be used to read or write to the tails of a
-- Cofree Comonad.
--
-- Using (^.) from the lens package:
--
--
-- foo ^. _unwrap == unwrap foo
--
--
-- For more on lenses see the lens package on hackage
--
--
-- _unwrap :: Lens' (Cofree g a) (g (Cofree g a))
--
_unwrap :: Functor f => (g (Cofree g a) -> f (g (Cofree g a))) -> Cofree g a -> f (Cofree g a)
-- | Construct an Lens into a Cofree g given a
-- list of lenses into the base functor. When the input list is empty,
-- this is equivalent to _extract. When the input list is
-- non-empty, this composes the input lenses with _unwrap to walk
-- through the Cofree g before using _extract to
-- get the element at the final location.
--
-- For more on lenses see the lens package on hackage.
--
--
-- telescoped :: [Lens' (g (Cofree g a)) (Cofree g a)] -> Lens' (Cofree g a) a
--
--
--
-- telescoped :: [Traversal' (g (Cofree g a)) (Cofree g a)] -> Traversal' (Cofree g a) a
--
--
--
-- telescoped :: [Getter (g (Cofree g a)) (Cofree g a)] -> Getter (Cofree g a) a
--
--
--
-- telescoped :: [Fold (g (Cofree g a)) (Cofree g a)] -> Fold (Cofree g a) a
--
--
--
-- telescoped :: [Setter' (g (Cofree g a)) (Cofree g a)] -> Setter' (Cofree g a) a
--
telescoped :: Functor f => [(Cofree g a -> f (Cofree g a)) -> g (Cofree g a) -> f (g (Cofree g a))] -> (a -> f a) -> Cofree g a -> f (Cofree g a)
-- | Construct an Lens into a Cofree g given a
-- list of lenses into the base functor. The only difference between this
-- and telescoped is that telescoped focuses on a single
-- value, but this focuses on the entire remaining subtree. When the
-- input list is empty, this is equivalent to id. When the input
-- list is non-empty, this composes the input lenses with _unwrap
-- to walk through the Cofree g.
--
-- For more on lenses see the lens package on hackage.
--
--
-- telescoped :: [Lens' (g (Cofree g a)) (Cofree g a)] -> Lens' (Cofree g a) (Cofree g a)
--
--
--
-- telescoped :: [Traversal' (g (Cofree g a)) (Cofree g a)] -> Traversal' (Cofree g a) (Cofree g a)
--
--
--
-- telescoped :: [Getter (g (Cofree g a)) (Cofree g a)] -> Getter (Cofree g a) (Cofree g a)
--
--
--
-- telescoped :: [Fold (g (Cofree g a)) (Cofree g a)] -> Fold (Cofree g a) (Cofree g a)
--
--
--
-- telescoped :: [Setter' (g (Cofree g a)) (Cofree g a)] -> Setter' (Cofree g a) (Cofree g a)
--
telescoped_ :: Functor f => [(Cofree g a -> f (Cofree g a)) -> g (Cofree g a) -> f (g (Cofree g a))] -> (Cofree g a -> f (Cofree g a)) -> Cofree g a -> f (Cofree g a)
-- | A Traversal' that gives access to all non-leaf a
-- elements of a Cofree g a, where non-leaf is defined as
-- x from (x :< xs) where null xs is
-- False.
--
-- Because this doesn't give access to all values in the
-- Cofree g, it cannot be used to change types.
--
--
-- shoots :: Traversable g => Traversal' (Cofree g a) a
--
--
-- N.B. On GHC < 7.9, this is slightly less flexible, as it has to use
-- null (toList xs) instead.
shoots :: (Applicative f, Traversable g) => (a -> f a) -> Cofree g a -> f (Cofree g a)
-- | A Traversal' that gives access to all leaf a
-- elements of a Cofree g a, where leaf is defined as
-- x from (x :< xs) where null xs is
-- True.
--
-- Because this doesn't give access to all values in the
-- Cofree g, it cannot be used to change types.
--
--
-- shoots :: Traversable g => Traversal' (Cofree g a) a
--
--
-- N.B. On GHC < 7.9, this is slightly less flexible, as it has to use
-- null (toList xs) instead.
leaves :: (Applicative f, Traversable g) => (a -> f a) -> Cofree g a -> f (Cofree g a)
instance (Data.Typeable.Internal.Typeable f, Data.Data.Data (f (Control.Comonad.Cofree.Cofree f a)), Data.Data.Data a) => Data.Data.Data (Control.Comonad.Cofree.Cofree f a)
instance GHC.Base.Functor f => Control.Comonad.Cofree.Class.ComonadCofree f (Control.Comonad.Cofree.Cofree f)
instance Data.Distributive.Distributive f => Data.Distributive.Distributive (Control.Comonad.Cofree.Cofree f)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Comonad.Cofree.Cofree f)
instance GHC.Base.Functor f => Data.Functor.Extend.Extend (Control.Comonad.Cofree.Cofree f)
instance GHC.Base.Functor f => Control.Comonad.Comonad (Control.Comonad.Cofree.Cofree f)
instance Control.Comonad.Trans.Class.ComonadTrans Control.Comonad.Cofree.Cofree
instance GHC.Base.Alternative f => GHC.Base.Monad (Control.Comonad.Cofree.Cofree f)
instance (GHC.Base.Alternative f, Control.Monad.Zip.MonadZip f) => Control.Monad.Zip.MonadZip (Control.Comonad.Cofree.Cofree f)
instance Data.Functor.Bind.Class.Apply f => Data.Functor.Bind.Class.Apply (Control.Comonad.Cofree.Cofree f)
instance Control.Comonad.ComonadApply f => Control.Comonad.ComonadApply (Control.Comonad.Cofree.Cofree f)
instance GHC.Base.Alternative f => GHC.Base.Applicative (Control.Comonad.Cofree.Cofree f)
instance Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show1 (Control.Comonad.Cofree.Cofree f)
instance (Data.Functor.Classes.Show1 f, GHC.Show.Show a) => GHC.Show.Show (Control.Comonad.Cofree.Cofree f a)
instance Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read1 (Control.Comonad.Cofree.Cofree f)
instance (Data.Functor.Classes.Read1 f, GHC.Read.Read a) => GHC.Read.Read (Control.Comonad.Cofree.Cofree f a)
instance (Data.Functor.Classes.Eq1 f, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Comonad.Cofree.Cofree f a)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq1 (Control.Comonad.Cofree.Cofree f)
instance (Data.Functor.Classes.Ord1 f, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Comonad.Cofree.Cofree f a)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord1 (Control.Comonad.Cofree.Cofree f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Comonad.Cofree.Cofree f)
instance Data.Semigroup.Foldable.Class.Foldable1 f => Data.Semigroup.Foldable.Class.Foldable1 (Control.Comonad.Cofree.Cofree f)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Comonad.Cofree.Cofree f)
instance Data.Semigroup.Traversable.Class.Traversable1 f => Data.Semigroup.Traversable.Class.Traversable1 (Control.Comonad.Cofree.Cofree f)
instance Control.Comonad.Hoist.Class.ComonadHoist Control.Comonad.Cofree.Cofree
instance Control.Comonad.Env.Class.ComonadEnv e w => Control.Comonad.Env.Class.ComonadEnv e (Control.Comonad.Cofree.Cofree w)
instance Control.Comonad.Store.Class.ComonadStore s w => Control.Comonad.Store.Class.ComonadStore s (Control.Comonad.Cofree.Cofree w)
instance Control.Comonad.Traced.Class.ComonadTraced m w => Control.Comonad.Traced.Class.ComonadTraced m (Control.Comonad.Cofree.Cofree w)