T      !"#$%&'()*+,-./0123456789: ; < = > ? @ A B C D E F G H I J K L M N O P Q R S non-portable (fundeps, MPTCs) experimentalEdward Kmett <ekmett@gmail.com> Safe-InferredMonads provide substitution (T) and renormalization (U):  m V f = U (T f m)A free Wp is one that does no work during the normalization step beyond simply grafting the two monadic values together. [] is not a free W (in this sense) because U [[a]] smashes the lists flat. On the other hand, consider:   - data Tree a = Bin (Tree a) (Tree a) | Tip a    instance W Tree where  X = Tip  Tip a V f = f a  Bin l r V f = Bin (l V f) (r V f) This W is the free W 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 W instance.  Moreover, Control.Monad.Free.Church provides a   instance that can improve the  asymptotic complexity of code that @ constructs free monads by effectively reassociating the use of  (V+). You may also want to take a look at the kan-extensions  package ( 1http://hackage.haskell.org/package/kan-extensions). See  * for a more formal definition of the free W  for a Y.  Add a layer.  . wrap (fmap f x) "a wrap (fmap return x) >>= f >A version of lift that can be used with just a Functor for f. <A version of wrap for monad transformers over a free monad. Note:- that this is the default implementation for  for  MonadFree f (t m). Z[\]^_`abcdeZ[\]^_`abcdeMPTCs, 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   :: (W m, Y 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 ) f ghijklmnopqrstuvwxyz{|}~    % f ghijklmnopqrstuvwxyz{|}~MPTCs, fundeps provisionalEdward Kmett <ekmett@gmail.com>None 7The monad supporting iteration based over a base monad m.     ~ FreeT   is the left inverse of     .  =   Tear down a Free W using iteration. Lift a monad homomorphism from m to n into a Monad homomorphism from   m to   n. EThis is not a true monad transformer. It is only a monad transformer "up to ". *     & MPTCs, fundeps provisionalEdward Kmett <ekmett@gmail.com>NoneThe   for a Y 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  W 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  W for a Y f. Formally A W n is a free W 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 W, leaving only the Y. i.e.  U (M,X,) = 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 W5 homomorphisms (natural transformations that respect X and ). *Morphisms in the category of functors are Y* 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  (V)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 V is fairly naive about the encoding. For more efficient free monad implementation see Control.Monad.Free.Church, in particular note the  combinator. ) You may also want to take a look at the kan-extensions package ( 1http://hackage.haskell.org/package/kan-extensions). 0A number of common monads arise as free monads,  Given  data Empty a,  Empty is isomorphic to the  monad.   q 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  W 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 (V) for ( than it is to (V) with .  6http://comonad.com/reader/2011/free-monads-for-less-2/ +Like iter for monadic values. ,, is the left inverse of  and    , .  =   , .  =  -.Convert to another free monad representation. .,Generate a Church-encoded free monad from a  monad. /iImprove 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 ()*+,-./ ()*+,-./ ()*/-+.,()*+,-./fundeps, MPTCs experimentalEdward Kmett <ekmett@gmail.com> Safe-Inferred01Allows you to peel a layer off a cofree comonad. 1Remove a layer. 01010101MPTCs, fundeps provisionalEdward Kmett <ekmett@gmail.com>None2)This is a cofree comonad of some functor f, with a comonad w$ threaded through it at each level. 5<This is the base functor of the cofree comonad transformer. 7%Extract the head of the base functor 8&Extract the tails of the base functor 9 Unfold a CofreeT> comonad transformer from a coalgebra and an initial comonad. "23456789      0123456789 234560178923456789      MPTCs, fundeps provisionalEdward Kmett <ekmett@gmail.com>None::This is the (co?)iterative comonad generated by a comonad = Unfold a CoiterTK comonad transformer from a cokleisli arrow and an initial comonadic seed. :;<= 01:;<=:;<01=:;<= MPTCs, fundeps provisionalEdward Kmett <ekmett@gmail.com>None>The > ! of a functor f. Formally A ! v is a cofree ! 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 " and  #, leaving you with only a Y. 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,  > + forms the a comonad for a non-empty list.  > ($ 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 = A (%  f)A%Unfold a cofree comonad from a seed. B & . B = %CDThis is a lens that can be used to read or write from the target of ". Using (^.) from the lens package:  foo ^. C == " fooFor more on lenses see the lens package on hackage C :: Lens' (> g a) aDCThis is a lens that can be used to read or write to the tails of a > !. Using (^.) from the lens package:  foo ^. D == 1 fooFor more on lenses see the lens package on hackage D :: Lens' (> g a) (g (> g a))E 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 :: Y g => [Lens' (> g a) (g (> g a))] -> Lens' (> g a) a'This is not a true !/ transformer, but this instance is convenient. #>?@AB()*CDE+,-./0123456789:;<'=>?@A 01>?@ABCDE >?01B@ACDE">?@AB()*CDE+,-./0123456789:;<'=>?@A GADTs, Rank2Types provisionalEdward Kmett <ekmett@gmail.com>NoneF The free B for a Y f. J$Given a natural transformation from f to g>, this gives a canonical monoidal natural transformation from F f to g. K A version of lift that can be used with just a Y for f. L$Given a natural transformation from f to g3 this gives a monoidal natural transformation from Alt f to Alt g. FGHIJKLCDEFGHIJFGHIJKLFIHGJKL FIHGJKLCDEFGHIJ GADTs, Rank2Types provisionalEdward Kmett <ekmett@gmail.com>NoneM The free K for a Y f. P$Given a natural transformation from f to g>, this gives a canonical monoidal natural transformation from M f to g. Q A version of lift that can be used with just a Y for f. R$Given a natural transformation from f to g3 this gives a monoidal natural transformation from Ap f to Ap g. MNOPQRSLMNOPMNOPQRSMONPQRS MONPQRSLMNOPQ   !"#$%&' ( %&)*  %&)*+,--.)%/01233456789 : : ; 9 < 6 = > ? @ A B C C D  E F G D D  H I J KLMNLLMOLMPLMQLMRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~LMLbcLbc LL                        ! " # $L% & ' ( ) * + , -L. / 0 1 2 34free-4.2Control.Monad.Free.ClassControl.Monad.Trans.FreeControl.Monad.Trans.IterControl.MonadPlus.FreeControl.Monad.FreeControl.Monad.Free.ChurchControl.Comonad.Cofree.ClassControl.Comonad.Trans.CofreeControl.Comonad.Trans.CoiterControl.Comonad.CofreeControl.Alternative.FreeControl.Applicative.FreeFree Control.Monadjoinimprove Data.FunctorIdentity Control.Arrow&&& MonadFreewrapliftFwrapTFreeTrunFreeTFreeFPureiterT hoistFreeT transFreeTIterTrunIterTIterFIterdelayretractiter hoistIterTPlusiterM hoistFree_Pure_FreeFrunFfromFtoF ComonadCofreeunwrapCofreeT runCofreeTCofreeF:<headFtailFcoiterTCoiterT runCoiterTCofreecoiterunfoldsection_extract_unwrap telescopedAltAprunAltliftAlthoistAltrunApliftAphoistAp retractApbaseGHC.Basefmap>>=MonadreturnFunctor$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$fFunctorFreeFtransformers-0.3.0.0Data.Functor.IdentityControl.Monad.Trans.Classliftid$fMonadTransIterTiterF freeTyCon iterConstr iterDataType $fDataIterT$fTypeable1IterT$fMonadFreeIdentityIterT$fMonadStatesIterT$fMonadReadereIterT$fTraversable1IterT$fTraversableIterT$fFoldable1IterT$fFoldableIterT$fMonadPlusIterT$fAlternativeIterT$fMonadFixIterT $fBindIterT $fApplyIterT $fMonadIterT$fApplicativeIterT$fFunctorIterT $fReadIterT $fShowIterT $fOrdIterT $fEqIterT$fBitraversableIterF$fBifoldableIterF$fBifunctorIterF$fTraversableIterF$fFoldableIterF$fFunctorIterF MonadPlus$fMonadTransFree 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 Data.MaybeMaybe$fTraversable1Free$fFoldable1Free$fMonadFixFree $fMonadContF$fMonadWriterwF$fMonadReadereF$fMonadStatesF $fMonadFreefF $fMonadTransF $fMonadPlusF$fMonadF$fBindF$fAlternativeF$fApplicativeF$fApplyF $fFunctorF$fComonadCofreefTracedT$fComonadCofreefStoreT$fComonadCofreefEnvT$fComonadCofreefIdentityT$fComonadCofreeConst(,)$fComonadCofreeMaybeNonEmpty cofreeTTyCon cofreeFTyCon cofreeFConstr cofreeTConstrcofreeFDataTypecofreeTDataType $fDataCofreeT $fDataCofreeF$fTypeable1CofreeT$fTypeable2CofreeF $fOrdCofreeT $fEqCofreeT $fReadCofreeT $fShowCofreeT$fComonadCofreefCofreeT$fComonadTransCofreeT$fTraversableCofreeT$fFoldableCofreeT$fComonadCofreeT$fFunctorCofreeT$fBitraversableCofreeF$fBifoldableCofreeF$fBifunctorCofreeF$fTraversableCofreeF$fFoldableCofreeF$fFunctorCofreeF coiterTTyCon coiterTConstrcoiterTDataType $fDataCoiterT$fTypeable1CoiterT $fOrdCoiterT $fEqCoiterT $fReadCoiterT $fShowCoiterT$fComonadCofreeIdentityCoiterT$fComonadTransCoiterT$fTraversableCoiterT$fFoldableCoiterT$fComonadCoiterT$fFunctorCoiterT comonad-4.0Control.ComonadComonadextract duplicateControl.ApplicativeConstControl.CategoryControl.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$fComonadCofreefCofree AlternativealtTyCon$fTypeable1Alt $fMonoidAlt$fSemigroupAlt$fAlternativeAlt$fApplicativeAlt $fApplyAlt $fFunctorAlt ApplicativeapTyCon $fTypeable1Ap$fApplicativeAp $fApplyAp $fFunctorAp