-- 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 4.8 -- | Automatic generation of free monadic actions. module Control.Monad.Free.TH -- | $(makeFree ''Type) provides free monadic actions for the -- constructors of the given type. makeFree :: Name -> Q [Dec] instance Show Arg -- | 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
--

--   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 -- | 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)
--

--   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 where wrap = join . lift . wrap . fmap return wrap :: MonadFree f m => f (m a) -> m a instance (Typeable1 m, Typeable a, Data (m (Either a (IterT m a))), Data a) => Data (IterT m a) instance Typeable1 m => Typeable1 (IterT m) instance (Monad m, Monoid a) => Monoid (IterT m a) instance Monad m => MonadFree Identity (IterT m) instance MonadCont m => MonadCont (IterT m) instance MonadIO m => MonadIO (IterT m) instance MonadError e m => MonadError e (IterT m) instance MonadState s m => MonadState s (IterT m) instance MonadWriter w m => MonadWriter w (IterT m) instance MonadReader e m => MonadReader e (IterT m) instance (Monad m, Traversable1 m) => Traversable1 (IterT m) instance (Monad m, Traversable m) => Traversable (IterT m) instance Foldable1 m => Foldable1 (IterT m) instance Foldable m => Foldable (IterT m) instance MonadTrans IterT instance MonadPlus m => MonadPlus (IterT m) instance MonadPlus m => Alternative (IterT m) instance MonadFix m => MonadFix (IterT m) instance Monad m => Bind (IterT m) instance Monad m => Apply (IterT m) instance Monad m => Monad (IterT m) instance Monad m => Applicative (IterT m) instance Monad m => Functor (IterT m) instance Read (m (Either a (IterT m a))) => Read (IterT m a) instance (Functor m, Read1 m) => Read1 (IterT m) instance Show (m (Either a (IterT m a))) => Show (IterT m a) instance (Functor m, Show1 m) => Show1 (IterT m) instance Ord (m (Either a (IterT m a))) => Ord (IterT m a) instance (Functor m, Ord1 m) => Ord1 (IterT m) instance Eq (m (Either a (IterT m a))) => Eq (IterT m a) instance (Functor m, Eq1 m) => Eq1 (IterT m) -- | 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 -- | Lift a natural transformation from f to g into a -- monad homomorphism from FreeT f m to FreeT -- g n transFreeT :: (Monad m, Functor g) => (forall a. f a -> g a) -> FreeT f m b -> FreeT g m b -- | 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) -- | 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)
--

--   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 where wrap = join . lift . wrap . fmap return wrap :: MonadFree f m => f (m a) -> m a instance Ord (m (FreeF f a (FreeT f m a))) => Ord (FreeT f m a) instance Eq (m (FreeF f a (FreeT f m a))) => Eq (FreeT f m a) instance (Eq a, Eq (f b)) => Eq (FreeF f a b) instance (Ord a, Ord (f b)) => Ord (FreeF f a b) instance (Show a, Show (f b)) => Show (FreeF f a b) instance (Read a, Read (f b)) => Read (FreeF f a b) instance (Typeable1 f, Typeable1 w, Typeable a, Data (w (FreeF f a (FreeT f w a))), Data a) => Data (FreeT f w a) instance (Typeable1 f, Typeable a, Typeable b, Data a, Data (f b), Data b) => Data (FreeF f a b) instance (Typeable1 f, Typeable1 w) => Typeable1 (FreeT f w) instance Typeable1 f => Typeable2 (FreeF f) instance (Monad m, Traversable m, Traversable f) => Traversable (FreeT f m) instance (Foldable m, Foldable f) => Foldable (FreeT f m) instance (Functor f, Monad m) => MonadFree f (FreeT f m) instance (Functor f, MonadPlus m) => MonadPlus (FreeT f m) instance (Functor f, MonadPlus m) => Alternative (FreeT f m) instance (Functor f, MonadCont m) => MonadCont (FreeT f m) instance (Functor f, MonadError e m) => MonadError e (FreeT f m) instance (Functor f, MonadState s m) => MonadState s (FreeT f m) instance (Functor f, MonadWriter w m) => MonadWriter w (FreeT f m) instance (Functor f, MonadReader r m) => MonadReader r (FreeT f m) instance (Functor f, MonadIO m) => MonadIO (FreeT f m) instance MonadTrans (FreeT f) instance (Functor f, Monad m) => Monad (FreeT f m) instance (Functor f, Monad m) => Bind (FreeT f m) instance (Functor f, Monad m) => Apply (FreeT f m) instance (Functor f, Monad m) => Applicative (FreeT f m) instance (Functor f, Monad m) => Functor (FreeT f m) instance Read (m (FreeF f a (FreeT f m a))) => Read (FreeT f m a) instance (Functor f, Read1 f, Functor m, Read1 m) => Read1 (FreeT f m) instance Show (m (FreeF f a (FreeT f m a))) => Show (FreeT f m a) instance (Functor f, Show1 f, Functor m, Show1 m) => Show1 (FreeT f m) instance (Functor f, Ord1 f, Functor m, Ord1 m) => Ord1 (FreeT f m) instance (Functor f, Eq1 f, Functor m, Eq1 m) => Eq1 (FreeT f m) instance Traversable f => Bitraversable (FreeF f) instance Foldable f => Bifoldable (FreeF f) instance Functor f => Bifunctor (FreeF f) instance Traversable f => Traversable (FreeF f a) instance Foldable f => Foldable (FreeF f a) instance Functor f => Functor (FreeF f a) instance (Ord1 f, Ord a) => Ord1 (FreeF f a) instance Ord1 f => Ord2 (FreeF f) instance (Eq1 f, Eq a) => Eq1 (FreeF f a) instance Eq1 f => Eq2 (FreeF f) instance (Read1 f, Read a) => Read1 (FreeF f a) instance Read1 f => Read2 (FreeF f) instance (Show1 f, Show a) => Show1 (FreeF f a) instance Show1 f => Show2 (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) -> (f (m r) -> m r) -> m r) -> FT f m a runFT :: FT f m a -> forall r. (a -> m r) -> (f (m r) -> 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 :: Functor f => (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) -- | Generate a Church-encoded free monad transformer from a FreeT -- monad transformer. toFT :: (Monad m, Functor f) => 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, Functor f) => (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 :: (Monad m, Functor g) => (forall a. f a -> g a) -> FT f m b -> FT g m b -- | 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 :: Functor f => Free f a -> F f a -- | retract is the left inverse of liftF -- --

--   retract . liftF = id
--

retract :: (Functor f, Monad f) => F f a -> f 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)
--

--   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
--

--   m >>= f = join (fmap f m)
--

--   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
--

--   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 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 -- | 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) -- | This is Prism' (Free f a) a in disguise -- --

--   >>> preview _Pure (Pure 3)
--   Just 3
--

-- --

--   >>> review _Pure 3 :: Free Maybe Int
--   Pure 3
--

_Pure :: (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 :: (Choice p, Applicative m) => p (f (Free f a)) (m (f (Free f a))) -> p (Free f a) (m (Free f a)) instance (Typeable1 f, Typeable a, Data a, Data (f (Free f a))) => Data (Free f a) instance Typeable1 f => Typeable1 (Free f) instance Functor f => MonadFree f (Free f) instance (Functor m, MonadCont m) => MonadCont (Free m) instance (Functor m, MonadError e m) => MonadError e (Free m) instance (Functor m, MonadState s m) => MonadState s (Free m) instance (Functor m, MonadReader e m) => MonadReader e (Free m) instance (Functor m, MonadWriter e m) => MonadWriter e (Free m) instance Traversable1 f => Traversable1 (Free f) instance Traversable f => Traversable (Free f) instance Foldable1 f => Foldable1 (Free f) instance Foldable f => Foldable (Free f) instance MonadTrans Free instance (Functor v, MonadPlus v) => MonadPlus (Free v) instance Alternative v => Alternative (Free v) instance Functor f => MonadFix (Free f) instance Functor f => Monad (Free f) instance Functor f => Bind (Free f) instance Functor f => Applicative (Free f) instance Functor f => Apply (Free f) instance Functor f => Functor (Free f) instance (Read (f (Free f a)), Read a) => Read (Free f a) instance (Functor f, Read1 f) => Read1 (Free f) instance (Show (f (Free f a)), Show a) => Show (Free f a) instance (Functor f, Show1 f) => Show1 (Free f) instance (Ord (f (Free f a)), Ord a) => Ord (Free f a) instance (Functor f, Ord1 f) => Ord1 (Free f) instance (Eq (f (Free f a)), Eq a) => Eq (Free f a) instance (Functor f, Eq1 f) => Eq1 (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: -- --

Free monads for less — Part 1
Free monads for less — Part 2

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: -- --

Free monads for less — Part 1
Free monads for less — Part 2

-- -- 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 -- | Like iter for monadic values. iterM :: (Monad m, Functor f) => (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 -- | Monads provide substitution (fmap) and renormalization -- (join): -- --

--   m >>= f = join (fmap f m)
--

--   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
--

--   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 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 -- | 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 (Eq a, Eq (f b)) => Eq (CofreeF f a b) instance (Ord a, Ord (f b)) => Ord (CofreeF f a b) instance (Show a, Show (f b)) => Show (CofreeF f a b) instance (Read a, Read (f b)) => Read (CofreeF f a b) instance (Typeable1 f, Typeable1 w, Typeable a, Data (w (CofreeF f a (CofreeT f w a))), Data a) => Data (CofreeT f w a) instance (Typeable1 f, Typeable a, Typeable b, Data a, Data (f b), Data b) => Data (CofreeF f a b) instance (Typeable1 f, Typeable1 w) => Typeable1 (CofreeT f w) instance Typeable1 f => Typeable2 (CofreeF f) instance (Alternative f, MonadZip f, MonadZip m) => MonadZip (CofreeT f m) instance Alternative f => MonadTrans (CofreeT f) instance (Alternative f, Applicative w) => Applicative (CofreeT f w) instance (Alternative f, Monad w) => Monad (CofreeT f w) instance Ord (w (CofreeF f a (CofreeT f w a))) => Ord (CofreeT f w a) instance Eq (w (CofreeF f a (CofreeT f w a))) => Eq (CofreeT f w a) instance Read (w (CofreeF f a (CofreeT f w a))) => Read (CofreeT f w a) instance Show (w (CofreeF f a (CofreeT f w a))) => Show (CofreeT f w a) instance (Functor f, Comonad w) => ComonadCofree f (CofreeT f w) instance Functor f => ComonadTrans (CofreeT f) instance (Traversable f, Traversable w) => Traversable (CofreeT f w) instance (Foldable f, Foldable w) => Foldable (CofreeT f w) instance (Functor f, Comonad w) => Comonad (CofreeT f w) instance (Functor f, Functor w) => Functor (CofreeT f w) instance Traversable f => Bitraversable (CofreeF f) instance Foldable f => Bifoldable (CofreeF f) instance Functor f => Bifunctor (CofreeF f) instance Traversable f => Traversable (CofreeF f a) instance Foldable f => Foldable (CofreeF f a) instance Functor f => Functor (CofreeF f a) -- | 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 unwrap :: ComonadCofree f w => w a -> f (w a) instance (Typeable1 w, Typeable a, Data (w (a, CoiterT w a)), Data a) => Data (CoiterT w a) instance Typeable1 w => Typeable1 (CoiterT w) instance Ord (w (a, CoiterT w a)) => Ord (CoiterT w a) instance Eq (w (a, CoiterT w a)) => Eq (CoiterT w a) instance Read (w (a, CoiterT w a)) => Read (CoiterT w a) instance Show (w (a, CoiterT w a)) => Show (CoiterT w a) instance ComonadStore s w => ComonadStore s (CoiterT w) instance ComonadTraced m w => ComonadTraced m (CoiterT w) instance ComonadHoist CoiterT instance ComonadEnv e w => ComonadEnv e (CoiterT w) instance Comonad w => ComonadCofree Identity (CoiterT w) instance ComonadTrans CoiterT instance Traversable w => Traversable (CoiterT w) instance Foldable w => Foldable (CoiterT w) instance Comonad w => Comonad (CoiterT w) instance Functor w => Functor (CoiterT w) instance (Functor w, Read1 w) => Read1 (CoiterT w) instance (Functor w, Show1 w) => Show1 (CoiterT w) instance (Functor w, Ord1 w) => Ord1 (CoiterT w) instance (Functor w, Eq1 w) => Eq1 (CoiterT w) -- | 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 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 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 -- | Unfold a cofree comonad from a seed. unfold :: Functor f => (b -> (a, f b)) -> b -> Cofree f 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 a Lens into a Cofree f given a list -- of lenses into the base functor. -- -- For more on lenses see the lens package on hackage. -- --

--   telescoped :: Functor g => [Lens' (Cofree g a) (g (Cofree g a))] -> Lens' (Cofree g a) a
--

telescoped :: (Functor f, Functor g) => [(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) instance ComonadTraced m w => ComonadTraced m (Cofree w) instance ComonadStore s w => ComonadStore s (Cofree w) instance ComonadEnv e w => ComonadEnv e (Cofree w) instance (Typeable1 f, Data (f (Cofree f a)), Data a) => Data (Cofree f a) instance (Typeable1 f, Typeable a) => Typeable (Cofree f a) instance Typeable1 f => Typeable1 (Cofree f) instance Traversable1 f => Traversable1 (Cofree f) instance Traversable f => Traversable (Cofree f) instance Foldable1 f => Foldable1 (Cofree f) instance Foldable f => Foldable (Cofree f) instance (Functor f, Ord1 f) => Ord1 (Cofree f) instance (Ord (f (Cofree f a)), Ord a) => Ord (Cofree f a) instance (Functor f, Eq1 f) => Eq1 (Cofree f) instance (Eq (f (Cofree f a)), Eq a) => Eq (Cofree f a) instance (Read (f (Cofree f a)), Read a) => Read (Cofree f a) instance (Functor f, Read1 f) => Read1 (Cofree f) instance (Show (f (Cofree f a)), Show a) => Show (Cofree f a) instance (Functor f, Show1 f) => Show1 (Cofree f) instance Alternative f => Applicative (Cofree f) instance ComonadApply f => ComonadApply (Cofree f) instance Apply f => Apply (Cofree f) instance (Alternative f, MonadZip f) => MonadZip (Cofree f) instance Alternative f => Monad (Cofree f) instance ComonadTrans Cofree instance Functor f => Comonad (Cofree f) instance Functor f => Extend (Cofree f) instance Functor f => Functor (Cofree f) instance Distributive f => Distributive (Cofree f) instance Functor f => ComonadCofree f (Cofree f) -- | 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 :: Alternative g => (forall x. f x -> g x) -> Alt f a -> g a -- | A version of lift that can be used with just a Functor -- for f. liftAlt :: Functor f => 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 Typeable1 f => Typeable1 (AltF f) instance Typeable1 f => Typeable1 (Alt f) instance Functor f => Monoid (Alt f a) instance Functor f => Semigroup (Alt f a) instance Functor f => Alternative (Alt f) instance Functor f => Apply (Alt f) instance Functor f => Applicative (Alt f) instance Functor f => Applicative (AltF f) instance Functor f => Functor (Alt f) instance Functor f => Functor (AltF 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 -- | 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 (Typeable1 f, Typeable1 g) => Typeable1 (ApF f g) instance (Typeable1 f, Typeable1 g) => Typeable1 (ApT f g) instance Alternative g => Alternative (ApT f g) instance Applicative g => Apply (ApT f g) instance Applicative g => Apply (ApF f g) instance Applicative g => Applicative (ApT f g) instance Applicative g => Applicative (ApF f g) instance Functor g => Functor (ApT f g) instance Functor g => Functor (ApF f g) -- | 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 -- | 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 Typeable1 f => Typeable1 (Ap f) instance Applicative (Ap f) instance Apply (Ap f) instance Functor (Ap f)