D      !"#$%&'()*+,-./01234567 8 9 : ; < = > ? @ A B C fundeps, MPTCs experimentalEdward Kmett <ekmett@gmail.com> Safe-Inferred1Allows you to peel a layer off a cofree comonad. Remove a layer. DEFGDEFGMPTCs, fundeps provisionalEdward Kmett <ekmett@gmail.com>None)This is a cofree comonad of some functor f, with a comonad w$ threaded through it at each level. <This is the base functor of the cofree comonad transformer. %Extract the head of the base functor &Extract the tails of the base functor  Unfold a CofreeT> comonad transformer from a coalgebra and an initial comonad. " HIJKLMNOPQRSTUVWXYZ[\]^_`a    HIJKLMNOPQRSTUVWXYZ[\]^_`aMPTCs, fundeps provisionalEdward Kmett <ekmett@gmail.com>None The   b of a functor f. Formally A b v is a cofree b for f if every comonad homomorphism  another comonad w to v+ is equivalent to a natural transformation  from w to f. A cofree2 functor is right adjoint to a forgetful functor. NCofree is a functor from the category of functors to the category of comonads N that is right adjoint to the forgetful functor from the category of comonads 1 to the category of functors that forgets how to c and  d, leaving you with only a e. KIn 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,    f+ forms the a comonad for a non-empty list.    (g b) is a product.    Identity forms an infinite stream.    ((->) b)'j describes a Moore machine with states labeled with values of type a, and transitions on edges of type b. :Use coiteration to generate a cofree comonad from a seed.   f =   (h    f) %Unfold a cofree comonad from a seed.  i .  = hDThis is a lens that can be used to read or write from the target of c. Using (^.) from the lens package:  foo ^.  == c fooFor more on lenses see the lens package on hackage  :: Lens' (  g a) aCThis is a lens that can be used to read or write to the tails of a   b. Using (^.) from the lens package:  foo ^.  ==  fooFor more on lenses see the lens package on hackage  :: Lens' (  g a) (g (  g a)) Construct a Lens into a   f/ given a list of lenses into the base functor. For more on lenses see the lens package on hackage. telescoped :: e g => [Lens' (  g a) (g (  g a))] -> Lens' (  g a) ajThis is not a true b/ transformer, but this instance is convenient. # klmnopqrstuvwxyz{|}~j    "  klmnopqrstuvwxyz{|}~jnon-portable (fundeps, MPTCs) experimentalEdward Kmett <ekmett@gmail.com> Safe-InferredMonads provide substitution () and renormalization ( ):  m  f =   .  f mA free p is one that does no work during the normalization step beyond simply grafting the two monadic values together. [] is not a free  (in this sense) because   [[a]] smashes the lists flat. On the other hand, consider:   - data Tree a = Bin (Tree a) (Tree a) | Tip a    instance  Tree where   = Tip  Tip a  f = f a  Bin l r  f = Bin (l  f) (r  f) This  is the free  of Pair:    data Pair a = Pair a a !And we could make an instance of  for it directly:    instance  Pair Tree where   (Pair l r) = Bin l r #Or we could choose to program with  Pair instead of Tree , and thereby avoid having to define our own  instance. Moreover, the kan-extensions package provides  instances that can  improve the  asymptotic5 complexity of code that constructors free monads by ' effectively reassociating the use of (). See * for a more formal definition of the free   for a e.  Add a layer. >A version of lift that can be used with just a Functor for f. MPTCs, fundeps provisionalEdward Kmett <ekmett@gmail.com>NoneThe "free monad transformer" for a functor f. #The base functor for a free monad. 4Tear down a free monad transformer using iteration. Lift a monad homomorphism from m to n into a monad homomorphism from  f m to  f n  :: ( m, e f) => (m ~> n) ->  f m ~>  f n#Lift a natural transformation from f to g into a monad homomorphism from  f m to  g n )  %MPTCs, fundeps provisionalEdward Kmett <ekmett@gmail.com>NoneThe   for a e f. Formally A  n is a free  for f! if every monadplus homomorphism  from n to another MonadPlus m+ is equivalent to a natural transformation  from f to m. 8We model this internally as if left-distribution holds.  ,http://www.haskell.org/haskellwiki/MonadPlus "" is the left inverse of  and    " .  =   " .  =  # Tear down a   using iteration. $Like iter for monadic values. %#Lift a natural transformation from f to g$ into a natural transformation from FreeT f to FreeT g. EThis is not a true monad transformer. It is only a monad transformer "up to "". % !"#$%  !"#$% ! "#$%"! "#$%MPTCs, fundeps provisionalEdward Kmett <ekmett@gmail.com>None &The &  for a e f. Formally A  n is a free  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 U9 from the category of monads to the category of functors  that just forgets the , leaving only the e. i.e.  U (M,, ) = Mthen & is the left adjoint to U. Being & being left adjoint to U, means that there is an isomorphism between & f -> m in the category of monads and f -> U m in the category of functors. (Morphisms in the category of monads are 5 homomorphisms (natural transformations that respect  and  ). *Morphisms in the category of functors are e* homomorphisms (natural transformations). 6Given this isomorphism, every monad homomorphism from & f to m0 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 & f a as many layers of f wrapped around values of type a, where  ()0 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 k is fairly naive about the encoding. For more efficient free monad implementations that require additional  extensions and thus aren'-t included here, you may want to look at the kan-extensions package. 0A number of common monads arise as free monads,  Given  data Empty a, & Empty is isomorphic to the  monad.  & fq can be used to model a partiality monad where each layer represents running the computation for a while longer. )) is the left inverse of  and    ) .  =   ) .  =  * Tear down a &  using iteration. +Like iter for monadic values. ,#Lift a natural transformation from f to g$ into a natural transformation from FreeT f to FreeT g. -This is Prism' (Free f a) a in disguise preview _Pure (Pure 3)Just 3 review _Pure 3 :: Free Maybe IntPure 3.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))EThis is not a true monad transformer. It is only a monad transformer "up to )". 4This violates the MonadPlus laws, handle with care. 6This violates the Alternative laws, handle with care. %&'()*+,-. &'()*+,-. &(')*+,-.#&(')*+,-."non-portable (rank-2 polymorphism) provisionalEdward Kmett <ekmett@gmail.com>None/,The Church-encoded free monad for a functor f. It is asymptotically more efficient to use () for / than it is to () with &.  6http://comonad.com/reader/2011/free-monads-for-less-2/ 2Like iter for monadic values. 33 is the left inverse of  and    3 .  =   3 .  =  4.Convert to another free monad representation. 5,Generate a Church-encoded free monad from a & monad. 6iImprove the asymptotic performance of code that builds a free monad with only binds and returns by using / behind the scenes. This is based on the "Free Monads for Less"% series of articles by Edward Kmett:  4http://comonad.com/reader/2011/free-monads-for-less/   6http://comonad.com/reader/2011/free-monads-for-less-2/ and "7Asymptotic Improvement of Computations over Free Monads" by Janis Voightlnder:  (http://www.iai.uni-bonn.de/~jv/mpc08.pdf /0123456 /0123456 /0164253/0123456 GADTs, Rank2Types provisionalEdward Kmett <ekmett@gmail.com>None7 The free  for a e f. ;$Given a natural transformation from f to g>, this gives a canonical monoidal natural transformation from 7 f to g. < A version of lift that can be used with just a e for f. =$Given a natural transformation from f to g3 this gives a monoidal natural transformation from Alt f to Alt g. 789:;<=789:;<=7:98;<= 7:98;<= GADTs, Rank2Types provisionalEdward Kmett <ekmett@gmail.com>None> The free  for a e f. A$Given a natural transformation from f to g>, this gives a canonical monoidal natural transformation from > f to g. B A version of lift that can be used with just a e for f. C$Given a natural transformation from f to g3 this gives a monoidal natural transformation from Ap f to Ap g. >?@ABC    >?@ABC>@?ABC >@?ABC      !"#$%%&'()*+,(-./0(-./012334/-567 8 8 9 ( : ; < 9 9 ( = > ?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`^_a^_bcdecfgchicjklmnopqrstuvwxyz{|}~cdcdcdcdc cdkch ch free-3.4.2Control.Comonad.Cofree.ClassControl.Comonad.Trans.CofreeControl.Comonad.CofreeControl.Monad.Free.ClassControl.Monad.Trans.FreeControl.MonadPlus.FreeControl.Monad.FreeControl.Monad.Free.ChurchControl.Alternative.FreeControl.Applicative.Free Control.Arrow&&& Control.MonadjoinFree Data.FunctorIdentity ComonadCofreeunwrapCofreeT runCofreeTCofreeF:<headFtailFcoiterTCofreecoiterunfoldsection_extract_unwrap telescoped MonadFreewrapliftFFreeTrunFreeTFreeFPureiterT hoistFreeT transFreeTPlusretractiteriterM hoistFree_Pure_FreeFrunFfromFtoFimproveAltAprunAltliftAlthoistAltrunApliftAphoistAp$fComonadCofreefTracedT$fComonadCofreefStoreT$fComonadCofreefEnvT$fComonadCofreefIdentityT cofreeTTyCon cofreeFTyCon cofreeFConstr cofreeTConstrcofreeFDataTypecofreeTDataType $fDataCofreeT $fDataCofreeF$fTypeable1CofreeT$fTypeable2CofreeF $fOrdCofreeT $fEqCofreeT $fReadCofreeT $fShowCofreeT$fComonadCofreefCofreeT$fComonadTransCofreeT$fTraversableCofreeT$fFoldableCofreeT$fComonadCofreeT$fFunctorCofreeT$fBitraversableCofreeF$fBifoldableCofreeF$fBifunctorCofreeF$fTraversableCofreeF$fFoldableCofreeF$fFunctorCofreeF comonad-3.1Control.ComonadComonadextract duplicatebaseGHC.BaseFunctor Data.MaybeMaybeControl.ApplicativeConstControl.Categoryidcomonad-transformers-3.1Control.Comonad.Trans.Classlower$fComonadTransCofree cofreeTyCon cofreeConstrcofreeDataType$fComonadTracedmCofree$fComonadStoresCofree$fComonadEnveCofree $fDataCofree$fTypeableCofree$fTypeable1Cofree$fTraversable1Cofree$fTraversableCofree$fFoldable1Cofree$fFoldableCofree $fOrdCofree $fEqCofree $fReadCofree $fShowCofree$fApplicativeCofree$fComonadApplyCofree $fApplyCofree $fMonadCofree$fComonadCofree$fExtendCofree$fFunctorCofree$fDistributiveCofree$fComonadCofreefCofreefmap>>=Monadreturn$fMonadFreefErrorT$fMonadFreefListT$fMonadFreefIdentityT$fMonadFreefMaybeT$fMonadFreefRWST$fMonadFreefRWST0$fMonadFreefWriterT$fMonadFreefWriterT0$fMonadFreefContT$fMonadFreefStateT$fMonadFreefStateT0$fMonadFreefReaderT transFreeF freeTTyCon freeFTyCon pureConstr freeConstr freeTConstr freeFDataType freeTDataType $fDataFreeT $fDataFreeF$fTypeable1FreeT$fTypeable2FreeF$fTraversableFreeT$fFoldableFreeT$fMonadFreefFreeT$fMonadPlusFreeT$fAlternativeFreeT$fMonadIOFreeT$fMonadTransFreeT $fMonadFreeT$fApplicativeFreeT$fFunctorFreeT $fReadFreeT $fShowFreeT $fOrdFreeT $fEqFreeT$fBitraversableFreeF$fBifoldableFreeF$fBifunctorFreeF$fTraversableFreeF$fFoldableFreeF$fFunctorFreeF MonadPlustransformers-0.3.0.0Control.Monad.Trans.Classlift$fMonadTransFree freeTyCon plusConstr freeDataType $fDataFree$fTypeable1Free$fMonadFreefFree$fMonadContFree$fMonadErroreFree$fMonadStatesFree$fMonadReadereFree$fMonadWritereFree$fTraversableFree$fFoldableFree $fMonoidFree$fSemigroupFree$fMonadPlusFree$fAlternativeFree $fMonadFree $fBindFree$fApplicativeFree $fApplyFree $fFunctorFree $fReadFree $fShowFree $fOrdFree$fEqFree$fTraversable1Free$fFoldable1Free $fMonadContF$fMonadWriterwF$fMonadReadereF$fMonadStatesF $fMonadFreefF $fMonadTransF $fMonadPlusF$fMonadF$fBindF$fAlternativeF$fApplicativeF$fApplyF $fFunctorF AlternativealtTyCon$fTypeable1Alt $fMonoidAlt$fSemigroupAlt$fAlternativeAlt$fApplicativeAlt $fApplyAlt $fFunctorAlt ApplicativeapTyCon $fTypeable1Ap$fApplicativeAp $fApplyAp $fFunctorAp