!       !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~           (C) 2013-2016 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> provisionalGADTs, TFs, MPTCs Trustworthy &'@AHVkan-extensionsA  6 functor (aka presheaf) suitable for Yoneda reduction. -http://ncatlab.org/nlab/show/Yoneda+reductionkan-extensions"Coyoneda "expansion" of a presheaf  .  "a    .  "a   kan-extensions Coyoneda reduction on a presheaf=(C) 2013-2016 Edward Kmett, Gershom Bazerman and Derek Elkins BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> provisionalportableNone 2EHSVX2 kan-extensions2The Day convolution of two contravariant functors. kan-extensionsConstruct the Day convolution  (  f g) = f  (  f g) = g kan-extensions>Break apart the Day convolution of two contravariant functors. kan-extensions_Day convolution provides a monoidal product. The associativity of this monoid is witnessed by   and  .   .   =     .   =     f     =       f kan-extensions_Day convolution provides a monoidal product. The associativity of this monoid is witnessed by   and  .   .   =     .   =     f     =       f kan-extensionsThe monoid for Day convolution  in Haskell is symmetric.   f     =       f kan-extensions,Proxy serves as the unit of Day convolution.     =     f    =      f kan-extensions,Proxy serves as the unit of Day convolution.     =     f    =      f kan-extensions{In Haskell we can do general purpose elimination, but in a more general setting it is only possible to eliminate the unit.     =    =        f    =      f kan-extensions}In Haskell we can do general purpose elimination, but in a more general setting it is only possible to eliminate the unit.      =    =        f    =      f kan-extensions Diagonalize the Day convolution:     =       =        = a -> (a,a)   f .  =  .   f kan-extensionsJApply a natural transformation to the left-hand side of a Day convolution.HThis respects the naturality of the natural transformation you supplied:   f    fg =  fg     f kan-extensionsKApply a natural transformation to the right-hand side of a Day convolution.HThis respects the naturality of the natural transformation you supplied:   f    fg =  fg     f   (C) 2013-2016 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> provisionalGADTs, TFs, MPTCs Trustworthy &'@AHSVX7)kan-extensionsYoneda embedding for a presheafkan-extensions  .  "a    .  "a   (C) 2014-2016 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> provisionalportableSafe 2EHSVXO kan-extensions.The Day convolution of two covariant functors.!kan-extensionsConstruct the Day convolution"kan-extensions_Day convolution provides a monoidal product. The associativity of this monoid is witnessed by " and #. " . # =  # . " =   f  " = "   f #kan-extensions_Day convolution provides a monoidal product. The associativity of this monoid is witnessed by " and #. " . # =  # . " =   f  # = #   f $kan-extensionsThe monoid for > convolution on the cartesian monoidal structure is symmetric.  f  $ = $   f %kan-extensions is the unit of  convolution %  ' =  '  % =  &kan-extensions is the unit of  convolution &  ( =  (  & =  'kan-extensions is the unit of  convolution %  ' =  '  % =  (kan-extensions is the unit of  convolution &  ( =  (  & =  )kan-extensions Collapse via a monoidal functor. ) (! f g) = f  g *kan-extensionsJApply a natural transformation to the left-hand side of a Day convolution.HThis respects the naturality of the natural transformation you supplied:  f  * fg = * fg   f +kan-extensionsKApply a natural transformation to the right-hand side of a Day convolution.HThis respects the naturality of the natural transformation you supplied:  f  + fg = + fg   f -kan-extensions&Proposition 4.1 from Pastro and Street !"#$%&'()*+,- !)"#$%&'(*+,-#2013-2016 Edward Kmett and Dan DoelBSDEdward Kmett <ekmett@gmail.com> experimental rank N typesSafe&'SXc 8kan-extensions The natural isomorphism between f and  Curried f f.  9   8 "a   8   9 "a   9 (8 x) -- definition 9 (5 ( x)) -- definition ( x) (  ) -- beta reduction    . x -- Applicative identity law x 9kan-extensionsLower 5 by applying    to the continuation.See 8.:kan-extensions3Indexed applicative composition of right Kan lifts.;kan-extensionsThis is the counit of the Day f -| Curried f adjunction<kan-extensionsThis is the unit of the Day f -| Curried f adjunction=kan-extensionsThe universal property of 5>kan-extensions = . > "a   > . = "a   ?kan-extensionsCurried f Identity a' is isomorphic to the right adjoint to f if one exists. ? . @ "a   @ . ? "a   @kan-extensionsCurried f Identity a' is isomorphic to the right adjoint to f if one exists.Akan-extensions Curried f h a? is isomorphic to the post-composition of the right adjoint of f onto h if such a right adjoint exists. A . B "a   B . A "a   Bkan-extensions Curried f h a? is isomorphic to the post-composition of the right adjoint of f onto h if such a right adjoint exists.56789:;<=>?@AB567=>;<?@BA89:(C) 2018 Brian Mckenna BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> provisionalportableNoneESX| Ekan-extensions.The Day convolution of two invariant functors.Gkan-extensionsConstruct the Day convolutionHkan-extensions_Day convolution provides a monoidal product. The associativity of this monoid is witnessed by H and I. H . I =   I . H =    f g   H = H    f g Ikan-extensions_Day convolution provides a monoidal product. The associativity of this monoid is witnessed by H and I. H . I =   I . H =    f g   I = I    f g Jkan-extensionsThe monoid for E> convolution on the cartesian monoidal structure is symmetric.  f g   J = J    f g Kkan-extensions is the unit of E convolution K   M =   M   K =   Lkan-extensions is the unit of E convolution L   N =   N   L =   Mkan-extensions is the unit of E convolution K   M =   M   K =   Nkan-extensions is the unit of E convolution L   N =   N   L =   Okan-extensionsJApply a natural transformation to the left-hand side of a Day convolution.HThis respects the naturality of the natural transformation you supplied:  f g   O fg = O fg    f g Pkan-extensionsKApply a natural transformation to the right-hand side of a Day convolution.HThis respects the naturality of the natural transformation you supplied:  f g   P fg = P fg    f g Qkan-extensions/Drop the covariant part of the Day convolution.Rkan-extensions3Drop the contravariant part of the Day convolution.EFGHIJKLMNOPQREFGHIJKLMNOPQR2008-2016 Edward KmettBSDEdward Kmett <ekmett@gmail.com> experimental rank 2 typesSafe&'-HSXTkan-extensionsThe left Kan extension of a  h along a  g.Vkan-extensions/The universal property of a left Kan extension.Wkan-extensionsW and V. witness a (higher kinded) adjunction between T g and (Compose g) V . W "a   W . V "a   Xkan-extensions X . Y "a   Y . X "a   Zkan-extensionsZ and [) witness the natural isomorphism between Lan f h and  Compose h g given f -| g [ . Z "a   Z . [ "a   \kan-extensions\ and ]& witness the natural isomorphism from Lan f (Lan g h) and Lan (f o g) h \ . ] "a   ] . \ "a   ^kan-extensionsEThis is the natural transformation that defines a Left Kan extension. TUVWXYZ[\]^ TUVW^\]XY[Z(C) 2011-2016 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> provisionalGADTs, MPTCs, fundeps Trustworthy &'>@AHSVX bkan-extensions A covariant  suitable for Yoneda reductiondkan-extensions Coyoneda f is the left Kan extension of f along the  functor. Coyoneda f is always a functor, even if f) is not. In this case, it is called the free functor over f1. Note the following categorical fine print: If f is not a functor,  Coyoneda f, is actually not the left Kan extension of f along the L functor, but along the inclusion functor from the discrete subcategory of HaskK which contains only identity functions as morphisms to the full category Hask. (This is because f, not being a proper functor, can only be interpreted as a categorical functor by restricting the source category to only contain identities.) d . e "a   e . d "a   fkan-extensionsYoneda "expansion" f . g "a   g . f "a    lowerCoyoneda (liftCoyoneda fa) = -- by definition lowerCoyoneda (Coyoneda id fa) = -- by definition fmap id fa = -- functor law fa  = f gkan-extensions>Yoneda reduction lets us walk under the existential and apply .NMnemonically, "Yoneda reduction" sounds like and works a bit like -reduction. -http://ncatlab.org/nlab/show/Yoneda+reduction You can view b as just the arguments to  tupled up.  = h = g hkan-extensionsYoneda reduction given a . lets us walk under the existential and apply . You can view b as just the arguments to  tupled up.  = h = g ikan-extensions#Lift a natural transformation from f to g# to a natural transformation from  Coyoneda f to  Coyoneda g.bcdefghibcfghide (C) 2008-2016 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalnon-portable (GADTs, MPTCs)Safe&'-@AH kan-extensions"The natural transformation from a  w to the  generated by w (forwards).,This is merely a right-inverse (section) of , rather than a full inverse.  .  "a   kan-extensions The Density ( of a left adjoint is isomorphic to the  formed by that .!This isomorphism is witnessed by  and .  .  "a    .  "a   kan-extensionsThe   of a  f0 is obtained by taking the left Kan extension (T) of f0 along itself. This isomorphism is witnessed by  and   .  "a    .  "a    (C) 2011-2016 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> provisional"non-portable (rank-2 polymorphism)Safe -=>?@AHSXkan-extensions  w a ~  w  a  2008-2016 Edward KmettBSDEdward Kmett <ekmett@gmail.com> experimental rank 2 types Trustworthy&'-HSXkan-extensionsThe right Kan extension of a  h along a  g.We can define a right Kan extension in several ways. The definition here is obtained by reading off the definition in of a right Kan extension in terms of an End, but we can derive an equivalent definition from the universal property.Given a   h : C -> D and a   g : C -> C', we want to extend h back along g to give Ran g h : C' -> D', such that the natural transformation  :: Ran g h (g a) -> h a exists.;In some sense this is trying to approximate the inverse of g^ by using one of its adjoints, because if the adjoint and the inverse both exist, they match! EHask -h-> Hask | + g / | Ran g h v / Hask -'_The Right Kan extension is unique (up to isomorphism) by taking this as its universal property.That is to say given any  K : C' -> D1 such that we have a natural transformation from k.g to h (forall x. k (g x) -> h x)6 there exists a canonical natural transformation from k to Ran g h. (forall x. k x -> Ran g h x).BWe could literally read this off as a valid Rank-3 definition for : data Ran' g h a = forall z. , z => Ran' (forall x. z (g x) -> h x) (z a) \This definition is isomorphic the simpler Rank-2 definition we use below as witnessed by the ?ranIso1 :: Ran g f x -> Ran' g f x ranIso1 (Ran e) = Ran' e id  PranIso2 :: Ran' g f x -> Ran g f x ranIso2 (Ran' h z) = Ran $ \k -> h (k <$> z)  ranIso2 (ranIso1 (Ran e)) "a -- by definition ranIso2 (Ran' e id) "a -- by definition Ran $ \k -> e (k <$> id) -- by definition Ran $ \k -> e (k . id) -- f . id = f Ran $ \k -> e k -- eta reduction Ran e :The other direction is left as an exercise for the reader.kan-extensions0The universal property of a right Kan extension.kan-extensions and * witness a higher kinded adjunction. from (`Compose' g) to  g  .  "a    .  "a   kan-extensions  .  "a    .  "a   kan-extensions  .  "a    .  "a   kan-extensions  .  "a    .  "a   kan-extensionsFThis is the natural transformation that defines a Right Kan extension. (C) 2008-2016 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> provisional"non-portable (rank-2 polymorphism) Trustworthy -.=?@AHSX6kan-extensions fB is the Monad generated by taking the right Kan extension of any  f along itself (Ran f f).5This can often be more "efficient" to construct than f( itself using repeated applications of (>>=).ySee "Asymptotic Improvement of Computations over Free Monads" by Janis Voigtlnder for more information about this type. ^https://www.janis-voigtlaender.eu/papers/AsymptoticImprovementOfComputationsOverFreeMonads.pdfkan-extensions2This serves as the *left*-inverse (retraction) of .  .  "a   HIn general this is not a full 2-sided inverse, merely a retraction, as  m% is often considerably "larger" than m.e.g. 0 ((->) s)) a ~ forall r. (a -> s -> r) -> s -> r% could support a full complement of  s actions, while (->) s is limited to  s actions.kan-extensionsThe H monad of a right adjoint is isomorphic to the monad obtained from the .  .  "a    .  "a   kan-extensionsThe  monad of a representable / is isomorphic to the monad obtained from the  for which that  is the right adjoint.  .  "a    .  "a   codensityToComposedRep =  .  kan-extensions  =  .  kan-extensionsThe   of a  g is the right Kan extension () of g along itself.  .  "a    .  "a   kan-extensionsFRight associate all binds in a computation that generates a free monadVThis can improve the asymptotic efficiency of the result, while preserving semantics.See "Asymptotic Improvement of Computations over Free Monads" by Janis Voightlnder for more information about this combinator. (http://www.iai.uni-bonn.de/~jv/mpc08.pdfkan-extensionsWrap the remainder of the " action using the given function.bThis function can be used to register cleanup actions that will be executed at the end. Example: *wrapCodensity (`finally` putStrLn "Done.") (C) 2011-2016 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> provisionalMPTCs, fundeps Trustworthy =>?@AHSVXLkan-extensions Yoneda f a- can be viewed as the partial application of  to its second argument.kan-extensions The natural isomorphism between f and  f, given by the Yoneda lemma is witnessed by  and   .  "a    .  "a    lowerYoneda (liftYoneda fa) = -- definition lowerYoneda (Yoneda (f -> fmap f a)) -- definition (f -> fmap f fa) id -- beta reduction fmap id fa -- functor law fa  =  kan-extensionsYoneda f- can be viewed as the right Kan extension of f along the  functor.  .  "a    .  "a    0! !"#$%%&'()*+,-.!"/0123#4567789:;<=>?@ABCDE,-!"FGHIIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrst u u v w x y z { | } ~         % % & ' ( ) *       (kan-extensions-5.2-6p5t6nFXmmC3k2OCKzSwX#Data.Functor.Contravariant.CoyonedaData.Functor.Contravariant.Day!Data.Functor.Contravariant.YonedaData.Functor.DayData.Functor.Day.CurriedData.Functor.Invariant.DayData.Functor.Kan.LanData.Functor.CoyonedaControl.Comonad.DensityControl.Monad.CoData.Functor.Kan.RanControl.Monad.CodensityData.Functor.YonedaData.Functor.Kan.RiftRiftCoyoneda liftCoyoneda lowerCoyoneda$fAdjunctionCoyonedaCoyoneda$fRepresentableCoyoneda$fContravariantCoyonedaDaydayrunDayassocdisassocswappedintro1intro2day1day2diagtrans1trans2$fRepresentableDay$fContravariantDayYoneda runYoneda liftYoneda lowerYoneda$fAdjunctionYonedaYoneda$fRepresentableYoneda$fContravariantYonedaelim1elim2dapcayleydayley$fComonadTransDay$fComonadApplyDay $fComonadDay$fDistributiveDay$fApplicativeDay $fFunctorDayCurried runCurried liftCurried lowerCurriedrapapplied unapplied toCurried fromCurriedadjointToCurriedcurriedToAdjointcurriedToComposedAdjointcomposedAdjointToCurried$fApplicativeCurried$fFunctorCurriedtoContravariant toCovariant$fInvariantDayLantoLanfromLan adjointToLan lanToAdjointlanToComposedAdjointcomposedAdjointToLan composeLan decomposeLanglan$fApplicativeLan $fApplyLan $fFunctorLan coyonedaToLan lanToCoyonedalowerM hoistCoyoneda $fOrdCoyoneda $fEqCoyoneda$fOrd1Coyoneda $fEq1Coyoneda$fReadCoyoneda$fShowCoyoneda$fRead1Coyoneda$fShow1Coyoneda$fDistributiveCoyoneda$fTraversable1Coyoneda$fTraversableCoyoneda$fFoldable1Coyoneda$fFoldableCoyoneda$fComonadTransCoyoneda$fComonadCoyoneda$fExtendCoyoneda$fMonadPlusCoyoneda$fMonadFixCoyoneda$fMonadTransCoyoneda$fMonadCoyoneda$fBindCoyoneda$fPlusCoyoneda $fAltCoyoneda$fAlternativeCoyoneda$fApplicativeCoyoneda$fApplyCoyoneda$fFunctorCoyonedaDensity liftDensitydensityToAdjunctionadjunctionToDensity lanToDensity densityToLan$fApplicativeDensity$fApplyDensity$fComonadTransDensity$fComonadDensity$fExtendDensity$fFunctorDensityCoTrunCoTCocorunColiftCoT0 lowerCoT0lowerCo0liftCoT1 lowerCoT1lowerCo1posWpeekWpeeksWaskWasksWtraceW liftCoT0M liftCoT1MditerdctrlM$fMonadErroreCoT$fMonadWritereCoT$fMonadStatesCoT$fMonadReadereCoT $fMonadIOCoT$fMonadTransCoT$fMonadFailCoT $fMonadCoT$fApplicativeCoT $fBindCoT $fApplyCoT $fFunctorCoTRanrunRantoRanfromRan composeRan decomposeRan adjointToRan ranToAdjointranToComposedAdjointcomposedAdjointToRangranrepToRanranToRepranToComposedRepcomposedRepToRan $fFunctorRan Codensity runCodensitylowerCodensitycodensityToAdjunctionadjunctionToCodensitycodensityToComposedRepcomposedRepToCodensitycodensityToRanranToCodensityimprove wrapCodensity$fMonadReaderrCodensity$fMonadStaterCodensity$fMonadFreefCodensity$fMonadPlusCodensity$fAlternativeCodensity$fPlusCodensity$fAltCodensity$fMonadTransCodensity$fMonadIOCodensity$fMonadFailCodensity$fMonadCodensity$fApplicativeCodensity$fApplyCodensity$fFunctorCodensity yonedaToRan ranToYonedamaxFminFmaxMminM$fComonadTransYoneda$fComonadYoneda$fExtendYoneda$fMonadFreefYoneda$fMonadTransYoneda$fMonadPlusYoneda$fMonadFixYoneda $fMonadYoneda $fBindYoneda$fAlternativeYoneda $fPlusYoneda $fAltYoneda $fOrdYoneda $fEqYoneda $fOrd1Yoneda $fEq1Yoneda $fReadYoneda $fShowYoneda $fRead1Yoneda $fShow1Yoneda$fDistributiveYoneda$fTraversable1Yoneda$fTraversableYoneda$fFoldable1Yoneda$fFoldableYoneda$fApplicativeYoneda $fApplyYoneda$fFunctorYonedabaseData.Functor.Contravariant ContravariantGHC.Baseid contramap. Data.TuplefstsndControl.CategoryfmapData.Functor.IdentityIdentity<*>pure&invariant-0.5.3-9W8Poinleji2BooR15Mx97Data.Functor.InvariantinvmapFunctortransformers-0.5.6.2Control.Monad.Trans.Classlift$comonad-5.0.5-JFdRPgecuFj5lQyTZW7sIKControl.Comonad.Trans.ClasslowerMonadliftMControl.ComonadComonad%adjunctions-4.4-WrZL0hr1y77fEXHVB5vmpData.Functor.Adjunction Adjunction mtl-2.2.2Control.Monad.State.Class MonadStateControl.Monad.Reader.Class MonadReaderon1