-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Kan extensions, Kan lifts, various forms of the Yoneda lemma, and (co)density (co)monads
--   
--   Kan extensions, Kan lifts, various forms of the Yoneda lemma, and
--   (co)density (co)monads
@package kan-extensions
@version 4.2.3


-- | Right and Left Kan lifts for functors over Hask, where they exist.
--   
--   <a>http://ncatlab.org/nlab/show/Kan+lift</a>
module Data.Functor.Kan.Rift

-- | <pre>
--   g . <a>Rift</a> g f =&gt; f
--   </pre>
--   
--   This could alternately be defined directly from the (co)universal
--   propertly in which case, we'd get <a>toRift</a> =
--   <tt>UniversalRift</tt>, but then the usage would suffer.
--   
--   <pre>
--   data <tt>UniversalRift</tt> g f a = forall z. <a>Functor</a> z =&gt;
--        <tt>UniversalRift</tt> (forall x. g (z x) -&gt; f x) (z a)
--   </pre>
--   
--   We can witness the isomorphism between Rift and UniversalRift using:
--   
--   <pre>
--   riftIso1 :: Functor g =&gt; UniversalRift g f a -&gt; Rift g f a
--   riftIso1 (UniversalRift h z) = Rift $ \g -&gt; h $ fmap (\k -&gt; k &lt;$&gt; z) g
--   </pre>
--   
--   <pre>
--   riftIso2 :: Rift g f a -&gt; UniversalRift g f a
--   riftIso2 (Rift e) = UniversalRift e id
--   </pre>
--   
--   <pre>
--   riftIso1 (riftIso2 (Rift h)) =
--   riftIso1 (UniversalRift h id) =          -- by definition
--   Rift $ \g -&gt; h $ fmap (\k -&gt; k &lt;$&gt; id) g -- by definition
--   Rift $ \g -&gt; h $ fmap id g               -- &lt;$&gt; = (.) and (.id)
--   Rift $ \g -&gt; h g                         -- by functor law
--   Rift h                                   -- eta reduction
--   </pre>
--   
--   The other direction is left as an exercise for the reader.
--   
--   There are several monads that we can form from <tt>Rift</tt>.
--   
--   When <tt>g</tt> is corepresentable (e.g. is a right adjoint) then
--   there exists <tt>x</tt> such that <tt>g ~ (-&gt;) x</tt>, then it
--   follows that
--   
--   <pre>
--   Rift g g a ~
--   forall r. (x -&gt; a -&gt; r) -&gt; x -&gt; r ~
--   forall r. (a -&gt; x -&gt; r) -&gt; x -&gt; r ~
--   forall r. (a -&gt; g r) -&gt; g r ~
--   Codensity g r
--   </pre>
--   
--   When <tt>f</tt> is a left adjoint, so that <tt>f -| g</tt> then
--   
--   <pre>
--   Rift f f a ~
--   forall r. f (a -&gt; r) -&gt; f r ~
--   forall r. (a -&gt; r) -&gt; g (f r) ~
--   forall r. (a -&gt; r) -&gt; Adjoint f g r ~
--   Yoneda (Adjoint f g r)
--   </pre>
--   
--   An alternative way to view that is to note that whenever <tt>f</tt> is
--   a left adjoint then <tt>f -| <a>Rift</a> f <a>Identity</a></tt>, and
--   since <tt><a>Rift</a> f f</tt> is isomorphic to <tt><a>Rift</a> f
--   <a>Identity</a> (f a)</tt>, this is the <a>Monad</a> formed by the
--   adjunction.
--   
--   <tt><a>Rift</a> <a>Identity</a> m</tt> can be a <a>Monad</a> for any
--   <a>Monad</a> <tt>m</tt>, as it is isomorphic to <tt><tt>Yoneda</tt>
--   m</tt>.
newtype Rift g h a
Rift :: (forall r. g (a -> r) -> h r) -> Rift g h a
[runRift] :: Rift g h a -> forall r. g (a -> r) -> h r

-- | The universal property of <a>Rift</a>
toRift :: (Functor g, Functor k) => (forall x. g (k x) -> h x) -> k a -> Rift g h a

-- | When <tt>f -| u</tt>, then <tt>f -| Rift f Identity</tt> and
--   
--   <pre>
--   <a>toRift</a> . <a>fromRift</a> ≡ <a>id</a>
--   <a>fromRift</a> . <a>toRift</a> ≡ <a>id</a>
--   </pre>
fromRift :: Adjunction f u => (forall a. k a -> Rift f h a) -> f (k b) -> h b
grift :: Adjunction f u => f (Rift f k a) -> k a

-- | <pre>
--   <a>composeRift</a> . <a>decomposeRift</a> ≡ <a>id</a>
--   <a>decomposeRift</a> . <a>composeRift</a> ≡ <a>id</a>
--   </pre>
composeRift :: (Composition compose, Adjunction g u) => Rift f (Rift g h) a -> Rift (compose g f) h a
decomposeRift :: (Composition compose, Functor f, Functor g) => Rift (compose g f) h a -> Rift f (Rift g h) a

-- | <tt>Rift f Identity a</tt> is isomorphic to the right adjoint to
--   <tt>f</tt> if one exists.
--   
--   <pre>
--   <a>adjointToRift</a> . <a>riftToAdjoint</a> ≡ <a>id</a>
--   <a>riftToAdjoint</a> . <a>adjointToRift</a> ≡ <a>id</a>
--   </pre>
adjointToRift :: Adjunction f u => u a -> Rift f Identity a

-- | <tt>Rift f Identity a</tt> is isomorphic to the right adjoint to
--   <tt>f</tt> if one exists.
riftToAdjoint :: Adjunction f u => Rift f Identity a -> u a

-- | <tt>Rift f h a</tt> is isomorphic to the post-composition of the right
--   adjoint of <tt>f</tt> onto <tt>h</tt> if such a right adjoint exists.
composedAdjointToRift :: (Functor h, Adjunction f u) => u (h a) -> Rift f h a

-- | <tt>Rift f h a</tt> is isomorphic to the post-composition of the right
--   adjoint of <tt>f</tt> onto <tt>h</tt> if such a right adjoint exists.
--   
--   <pre>
--   <a>riftToComposedAdjoint</a> . <a>composedAdjointToRift</a> ≡ <a>id</a>
--   <a>composedAdjointToRift</a> . <a>riftToComposedAdjoint</a> ≡ <a>id</a>
--   </pre>
riftToComposedAdjoint :: Adjunction f u => Rift f h a -> u (h a)

-- | The natural isomorphism between <tt>f</tt> and <tt>Rift f f</tt>. <tt>
--   <a>lowerRift</a> <a>.</a> <a>liftRift</a> ≡ <a>id</a> <a>liftRift</a>
--   <a>.</a> <a>lowerRift</a> ≡ <a>id</a> </tt>
--   
--   <pre>
--   <a>lowerRift</a> (<a>liftRift</a> x)     -- definition
--   <a>lowerRift</a> (<a>Rift</a> (<a>&lt;*&gt;</a> x))   -- definition
--   (<a>&lt;*&gt;</a> x) (<a>pure</a> <a>id</a>)          -- beta reduction
--   <a>pure</a> <a>id</a> <a>&lt;*&gt;</a> x              -- Applicative identity law
--   x
--   </pre>
liftRift :: Applicative f => f a -> Rift f f a

-- | Lower <a>Rift</a> by applying <a>pure</a> <a>id</a> to the
--   continuation.
--   
--   See <a>liftRift</a>.
lowerRift :: Applicative f => Rift f g a -> g a

-- | Indexed applicative composition of right Kan lifts.
rap :: Functor f => Rift f g (a -> b) -> Rift g h a -> Rift f h b
instance GHC.Base.Functor g => GHC.Base.Functor (Data.Functor.Kan.Rift.Rift g h)
instance (GHC.Base.Functor g, g ~ h) => GHC.Base.Applicative (Data.Functor.Kan.Rift.Rift g h)


-- | Left Kan lifts for functors over Hask, wherever they exist.
--   
--   <a>http://ncatlab.org/nlab/show/Kan+lift</a>
module Data.Functor.Kan.Lift

-- | <pre>
--   f =&gt; g . Lift g f
--   (forall z. f =&gt; g . z) -&gt; Lift g f =&gt; z -- couniversal
--   </pre>
--   
--   Here we use the universal property directly as how we extract from our
--   definition of <a>Lift</a>.
newtype Lift g f a
Lift :: (forall z. Functor z => (forall x. f x -> g (z x)) -> z a) -> Lift g f a
[runLift] :: Lift g f a -> forall z. Functor z => (forall x. f x -> g (z x)) -> z a

-- | The universal property of <a>Lift</a>
toLift :: Functor z => (forall a. f a -> g (z a)) -> Lift g f b -> z b

-- | When the adjunction exists
--   
--   <pre>
--   <a>fromLift</a> . <a>toLift</a> ≡ <a>id</a>
--   <a>toLift</a> . <a>fromLift</a> ≡ <a>id</a>
--   </pre>
fromLift :: Adjunction l u => (forall a. Lift u f a -> z a) -> f b -> u (z b)

-- | <pre>
--   f =&gt; g (<a>Lift</a> g f a)
--   </pre>
glift :: Adjunction l g => k a -> g (Lift g k a)

-- | <pre>
--   <a>composeLift</a> . <a>decomposeLift</a> = <a>id</a>
--   <a>decomposeLift</a> . <a>composeLift</a> = <a>id</a>
--   </pre>
composeLift :: (Composition compose, Functor f, Functor g) => Lift f (Lift g h) a -> Lift (compose g f) h a
decomposeLift :: (Composition compose, Adjunction l g) => Lift (compose g f) h a -> Lift f (Lift g h) a

-- | <tt>Lift u Identity a</tt> is isomorphic to the left adjoint to
--   <tt>u</tt> if one exists.
--   
--   <pre>
--   <a>adjointToLift</a> . <a>liftToAdjoint</a> ≡ <a>id</a>
--   <a>liftToAdjoint</a> . <a>adjointToLift</a> ≡ <a>id</a>
--   </pre>
adjointToLift :: Adjunction f u => f a -> Lift u Identity a

-- | <tt>Lift u Identity a</tt> is isomorphic to the left adjoint to
--   <tt>u</tt> if one exists.
liftToAdjoint :: Adjunction f u => Lift u Identity a -> f a

-- | <tt>Lift u h a</tt> is isomorphic to the post-composition of the left
--   adjoint of <tt>u</tt> onto <tt>h</tt> if such a left adjoint exists.
--   
--   <pre>
--   <a>liftToComposedAdjoint</a> . <a>composedAdjointToLift</a> ≡ <a>id</a>
--   <a>composedAdjointToLift</a> . <a>liftToComposedAdjoint</a> ≡ <a>id</a>
--   </pre>
liftToComposedAdjoint :: (Adjunction f u, Functor h) => Lift u h a -> f (h a)

-- | <tt>Lift u h a</tt> is isomorphic to the post-composition of the left
--   adjoint of <tt>u</tt> onto <tt>h</tt> if such a left adjoint exists.
composedAdjointToLift :: Adjunction f u => f (h a) -> Lift u h a

-- | <pre>
--   <a>repToLift</a> . <a>liftToRep</a> ≡ <a>id</a>
--   <a>liftToRep</a> . <a>repToLift</a> ≡ <a>id</a>
--   </pre>
repToLift :: Representable u => Rep u -> a -> Lift u Identity a
liftToRep :: Representable u => Lift u Identity a -> (Rep u, a)

-- | <pre>
--   <a>liftToComposedRep</a> . <a>composedRepToLift</a> ≡ <a>id</a>
--   <a>composedRepToLift</a> . <a>liftToComposedRep</a> ≡ <a>id</a>
--   </pre>
liftToComposedRep :: (Functor h, Representable u) => Lift u h a -> (Rep u, h a)
composedRepToLift :: Representable u => Rep u -> h a -> Lift u h a
instance GHC.Base.Functor (Data.Functor.Kan.Lift.Lift g h)


-- | Eitan Chatav first introduced me to this construction
--   
--   The Day convolution of two covariant functors is a covariant functor.
--   
--   Day convolution is usually defined in terms of contravariant functors,
--   however, it just needs a monoidal category, and Hask^op is also
--   monoidal.
--   
--   Day convolution can be used to nicely describe monoidal functors as
--   monoid objects w.r.t this product.
--   
--   <a>http://ncatlab.org/nlab/show/Day+convolution</a>
module Data.Functor.Day

-- | The Day convolution of two covariant functors.
--   
--   <tt>Day f g a -&gt; h a</tt> is isomorphic to <tt>f a -&gt; Rift g h
--   a</tt>
data Day f g a
Day :: (f b) -> (g c) -> (b -> c -> a) -> Day f g a

-- | Construct the Day convolution
day :: f (a -> b) -> g a -> Day f g b

-- | Collapse via a monoidal functor.
--   
--   <pre>
--   <a>dap</a> (<a>day</a> f g) = f <a>&lt;*&gt;</a> g
--   </pre>
dap :: Applicative f => Day f f a -> f a

-- | Day convolution provides a monoidal product. The associativity of this
--   monoid is witnessed by <a>assoc</a> and <a>disassoc</a>.
--   
--   <pre>
--   <a>assoc</a> . <a>disassoc</a> = <a>id</a>
--   <a>disassoc</a> . <a>assoc</a> = <a>id</a>
--   <a>fmap</a> f <a>.</a> <a>assoc</a> = <a>assoc</a> <a>.</a> <a>fmap</a> f
--   </pre>
assoc :: Day f (Day g h) a -> Day (Day f g) h a

-- | Day convolution provides a monoidal product. The associativity of this
--   monoid is witnessed by <a>assoc</a> and <a>disassoc</a>.
--   
--   <pre>
--   <a>assoc</a> . <a>disassoc</a> = <a>id</a>
--   <a>disassoc</a> . <a>assoc</a> = <a>id</a>
--   <a>fmap</a> f <a>.</a> <a>disassoc</a> = <a>disassoc</a> <a>.</a> <a>fmap</a> f
--   </pre>
disassoc :: Day (Day f g) h a -> Day f (Day g h) a

-- | The monoid for <a>Day</a> convolution on the cartesian monoidal
--   structure is symmetric.
--   
--   <pre>
--   <a>fmap</a> f <a>.</a> <a>swapped</a> = <a>swapped</a> <a>.</a> <a>fmap</a> f
--   </pre>
swapped :: Day f g a -> Day g f a

-- | <a>Identity</a> is the unit of <a>Day</a> convolution
--   
--   <pre>
--   <a>intro1</a> <a>.</a> <a>elim1</a> = <a>id</a>
--   <a>elim1</a> <a>.</a> <a>intro1</a> = <a>id</a>
--   </pre>
intro1 :: f a -> Day Identity f a

-- | <a>Identity</a> is the unit of <a>Day</a> convolution
--   
--   <pre>
--   <a>intro2</a> <a>.</a> <a>elim2</a> = <a>id</a>
--   <a>elim2</a> <a>.</a> <a>intro2</a> = <a>id</a>
--   </pre>
intro2 :: f a -> Day f Identity a

-- | <a>Identity</a> is the unit of <a>Day</a> convolution
--   
--   <pre>
--   <a>intro1</a> <a>.</a> <a>elim1</a> = <a>id</a>
--   <a>elim1</a> <a>.</a> <a>intro1</a> = <a>id</a>
--   </pre>
elim1 :: Functor f => Day Identity f a -> f a

-- | <a>Identity</a> is the unit of <a>Day</a> convolution
--   
--   <pre>
--   <a>intro2</a> <a>.</a> <a>elim2</a> = <a>id</a>
--   <a>elim2</a> <a>.</a> <a>intro2</a> = <a>id</a>
--   </pre>
elim2 :: Functor f => Day f Identity a -> f a

-- | Apply a natural transformation to the left-hand side of a Day
--   convolution.
--   
--   This respects the naturality of the natural transformation you
--   supplied:
--   
--   <pre>
--   <a>fmap</a> f <a>.</a> <a>trans1</a> fg = <a>trans1</a> fg <a>.</a> <a>fmap</a> f
--   </pre>
trans1 :: (forall x. f x -> g x) -> Day f h a -> Day g h a

-- | Apply a natural transformation to the right-hand side of a Day
--   convolution.
--   
--   This respects the naturality of the natural transformation you
--   supplied:
--   
--   <pre>
--   <a>fmap</a> f <a>.</a> <a>trans2</a> fg = <a>trans2</a> fg <a>.</a> <a>fmap</a> f
--   </pre>
trans2 :: (forall x. g x -> h x) -> Day f g a -> Day f h a
instance GHC.Base.Functor (Data.Functor.Day.Day f g)
instance (GHC.Base.Applicative f, GHC.Base.Applicative g) => GHC.Base.Applicative (Data.Functor.Day.Day f g)
instance (Data.Functor.Rep.Representable f, Data.Functor.Rep.Representable g) => Data.Distributive.Distributive (Data.Functor.Day.Day f g)
instance (Data.Functor.Rep.Representable f, Data.Functor.Rep.Representable g) => Data.Functor.Rep.Representable (Data.Functor.Day.Day f g)


-- | The co-Yoneda lemma for presheafs states that <tt>f</tt> is naturally
--   isomorphic to <tt><a>Coyoneda</a> f</tt>.
module Data.Functor.Contravariant.Coyoneda

-- | A <a>Contravariant</a> functor (aka presheaf) suitable for Yoneda
--   reduction.
--   
--   <a>http://ncatlab.org/nlab/show/Yoneda+reduction</a>
data Coyoneda f a
Coyoneda :: (a -> b) -> f b -> Coyoneda f a

-- | Coyoneda "expansion" of a presheaf
--   
--   <pre>
--   <a>liftCoyoneda</a> . <a>lowerCoyoneda</a> ≡ <a>id</a>
--   <a>lowerCoyoneda</a> . <a>liftCoyoneda</a> ≡ <a>id</a>
--   </pre>
liftCoyoneda :: f a -> Coyoneda f a

-- | Coyoneda reduction on a presheaf
lowerCoyoneda :: Contravariant f => Coyoneda f a -> f a
instance Data.Functor.Contravariant.Contravariant (Data.Functor.Contravariant.Coyoneda.Coyoneda f)
instance Data.Functor.Contravariant.Rep.Representable f => Data.Functor.Contravariant.Rep.Representable (Data.Functor.Contravariant.Coyoneda.Coyoneda f)
instance Data.Functor.Contravariant.Adjunction.Adjunction f g => Data.Functor.Contravariant.Adjunction.Adjunction (Data.Functor.Contravariant.Coyoneda.Coyoneda f) (Data.Functor.Contravariant.Coyoneda.Coyoneda g)


module Data.Functor.Contravariant.Yoneda

-- | Yoneda embedding for a presheaf
newtype Yoneda f a
Yoneda :: (forall r. (r -> a) -> f r) -> Yoneda f a
[runYoneda] :: Yoneda f a -> forall r. (r -> a) -> f r

-- | <pre>
--   <a>liftYoneda</a> . <a>lowerYoneda</a> ≡ <a>id</a>
--   <a>lowerYoneda</a> . <a>liftYoneda</a> ≡ <a>id</a>
--   </pre>
liftYoneda :: Contravariant f => f a -> Yoneda f a
lowerYoneda :: Yoneda f a -> f a
instance Data.Functor.Contravariant.Contravariant (Data.Functor.Contravariant.Yoneda.Yoneda f)
instance Data.Functor.Contravariant.Rep.Representable f => Data.Functor.Contravariant.Rep.Representable (Data.Functor.Contravariant.Yoneda.Yoneda f)
instance Data.Functor.Contravariant.Adjunction.Adjunction f g => Data.Functor.Contravariant.Adjunction.Adjunction (Data.Functor.Contravariant.Yoneda.Yoneda f) (Data.Functor.Contravariant.Yoneda.Yoneda g)


-- | The Day convolution of two contravariant functors is a contravariant
--   functor.
--   
--   <a>http://ncatlab.org/nlab/show/Day+convolution</a>
module Data.Functor.Contravariant.Day

-- | The Day convolution of two contravariant functors.
data Day f g a
Day :: (f b) -> (g c) -> (a -> (b, c)) -> Day f g a

-- | Construct the Day convolution
--   
--   <pre>
--   <a>day1</a> (<a>day</a> f g) = f
--   <a>day2</a> (<a>day</a> f g) = g
--   </pre>
day :: f a -> g b -> Day f g (a, b)

-- | Break apart the Day convolution of two contravariant functors.
runDay :: (Contravariant f, Contravariant g) => Day f g a -> (f a, g a)

-- | Day convolution provides a monoidal product. The associativity of this
--   monoid is witnessed by <a>assoc</a> and <a>disassoc</a>.
--   
--   <pre>
--   <a>assoc</a> . <a>disassoc</a> = <a>id</a>
--   <a>disassoc</a> . <a>assoc</a> = <a>id</a>
--   <a>contramap</a> f <a>.</a> <a>assoc</a> = <a>assoc</a> <a>.</a> <a>contramap</a> f
--   </pre>
assoc :: Day f (Day g h) a -> Day (Day f g) h a

-- | Day convolution provides a monoidal product. The associativity of this
--   monoid is witnessed by <a>assoc</a> and <a>disassoc</a>.
--   
--   <pre>
--   <a>assoc</a> . <a>disassoc</a> = <a>id</a>
--   <a>disassoc</a> . <a>assoc</a> = <a>id</a>
--   <a>contramap</a> f <a>.</a> <a>disassoc</a> = <a>disassoc</a> <a>.</a> <a>contramap</a> f
--   </pre>
disassoc :: Day (Day f g) h a -> Day f (Day g h) a

-- | The monoid for Day convolution <i>in Haskell</i> is symmetric.
--   
--   <pre>
--   <a>contramap</a> f <a>.</a> <a>swapped</a> = <a>swapped</a> <a>.</a> <a>contramap</a> f
--   </pre>
swapped :: Day f g a -> Day g f a

-- | Proxy serves as the unit of Day convolution.
--   
--   <pre>
--   <a>day1</a> <a>.</a> <a>intro1</a> = <a>id</a>
--   <a>contramap</a> f <a>.</a> <a>intro1</a> = <a>intro1</a> <a>.</a> <a>contramap</a> f
--   </pre>
intro1 :: f a -> Day Proxy f a

-- | Proxy serves as the unit of Day convolution.
--   
--   <pre>
--   <a>day2</a> <a>.</a> <a>intro2</a> = <a>id</a>
--   <a>contramap</a> f <a>.</a> <a>intro2</a> = <a>intro2</a> <a>.</a> <a>contramap</a> f
--   </pre>
intro2 :: f a -> Day f Proxy a

-- | In Haskell we can do general purpose elimination, but in a more
--   general setting it is only possible to eliminate the unit.
--   
--   <pre>
--   <a>day1</a> <a>.</a> <a>intro1</a> = <a>id</a>
--   <a>day1</a> = <a>fst</a> <a>.</a> <a>runDay</a>
--   <a>contramap</a> f <a>.</a> <a>day1</a> = <a>day1</a> <a>.</a> <a>contramap</a> f
--   </pre>
day1 :: Contravariant f => Day f g a -> f a

-- | In Haskell we can do general purpose elimination, but in a more
--   general setting it is only possible to eliminate the unit. <tt>
--   <a>day2</a> <a>.</a> <a>intro2</a> = <a>id</a> <a>day2</a> =
--   <a>snd</a> <a>.</a> <a>runDay</a> <a>contramap</a> f <a>.</a>
--   <a>day2</a> = <a>day2</a> <a>.</a> <a>contramap</a> f </tt>
day2 :: Contravariant g => Day f g a -> g a

-- | Diagonalize the Day convolution:
--   
--   <pre>
--   <a>day1</a> <a>.</a> <a>diag</a> = <a>id</a>
--   <a>day2</a> <a>.</a> <a>diag</a> = <a>id</a>
--   <a>runDay</a> <a>.</a> <a>diag</a> = a -&gt; (a,a)
--   <a>contramap</a> f . <a>diag</a> = <a>diag</a> . <a>contramap</a> f
--   </pre>
diag :: f a -> Day f f a

-- | Apply a natural transformation to the left-hand side of a Day
--   convolution.
--   
--   This respects the naturality of the natural transformation you
--   supplied:
--   
--   <pre>
--   <a>contramap</a> f <a>.</a> <a>trans1</a> fg = <a>trans1</a> fg <a>.</a> <a>contramap</a> f
--   </pre>
trans1 :: (forall x. f x -> g x) -> Day f h a -> Day g h a

-- | Apply a natural transformation to the right-hand side of a Day
--   convolution.
--   
--   This respects the naturality of the natural transformation you
--   supplied:
--   
--   <pre>
--   <a>contramap</a> f <a>.</a> <a>trans2</a> fg = <a>trans2</a> fg <a>.</a> <a>contramap</a> f
--   </pre>
trans2 :: (forall x. g x -> h x) -> Day f g a -> Day f h a
instance Data.Functor.Contravariant.Contravariant (Data.Functor.Contravariant.Day.Day f g)
instance (Data.Functor.Contravariant.Rep.Representable f, Data.Functor.Contravariant.Rep.Representable g) => Data.Functor.Contravariant.Rep.Representable (Data.Functor.Contravariant.Day.Day f g)


-- | <ul>
--   <li>Right Kan Extensions</li>
--   </ul>
module Data.Functor.Kan.Ran

-- | The right Kan extension of a <a>Functor</a> h along a <a>Functor</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 <a>Functor</a> <tt>h : C -&gt; D</tt> and a <a>Functor</a>
--   <tt>g : C -&gt; C'</tt>, we want to extend <tt>h</tt> <i>back</i>
--   along <tt>g</tt> to give <tt>Ran g h : C' -&gt; C</tt>, such that the
--   natural transformation <tt><a>gran</a> :: Ran g h (g a) -&gt; h a</tt>
--   exists.
--   
--   In some sense this is trying to approximate the inverse of <tt>g</tt>
--   by using one of its adjoints, because if the adjoint and the inverse
--   both exist, they match!
--   
--   <pre>
--   Hask -h-&gt; Hask
--     |       +
--     g      /
--     |    Ran g h
--     v    /
--   Hask -'
--   </pre>
--   
--   The Right Kan extension is unique (up to isomorphism) by taking this
--   as its universal property.
--   
--   That is to say given any <tt>K : C' -&gt; C</tt> such that we have a
--   natural transformation from <tt>k.g</tt> to <tt>h</tt> <tt>(forall x.
--   k (g x) -&gt; h x)</tt> there exists a canonical natural
--   transformation from <tt>k</tt> to <tt>Ran g h</tt>. <tt>(forall x. k x
--   -&gt; Ran g h x)</tt>.
--   
--   We could literally read this off as a valid Rank-3 definition for
--   <a>Ran</a>:
--   
--   <pre>
--   data Ran' g h a = forall z. <a>Functor</a> z =&gt; Ran' (forall x. z (g x) -&gt; h x) (z a)
--   </pre>
--   
--   This definition is isomorphic the simpler Rank-2 definition we use
--   below as witnessed by the
--   
--   <pre>
--   ranIso1 :: Ran g f x -&gt; Ran' g f x
--   ranIso1 (Ran e) = Ran' e id
--   </pre>
--   
--   <pre>
--   ranIso2 :: Ran' g f x -&gt; Ran g f x
--   ranIso2 (Ran' h z) = Ran $ \k -&gt; h (k &lt;$&gt; z)
--   </pre>
--   
--   <pre>
--   ranIso2 (ranIso1 (Ran e)) ≡ -- by definition
--   ranIso2 (Ran' e id) ≡       -- by definition
--   Ran $ \k -&gt; e (k &lt;$&gt; id)    -- by definition
--   Ran $ \k -&gt; e (k . id)      -- f . id = f
--   Ran $ \k -&gt; e k             -- eta reduction
--   Ran e
--   </pre>
--   
--   The other direction is left as an exercise for the reader.
newtype Ran g h a
Ran :: (forall b. (a -> g b) -> h b) -> Ran g h a
[runRan] :: Ran g h a -> forall b. (a -> g b) -> h b

-- | The universal property of a right Kan extension.
toRan :: Functor k => (forall a. k (g a) -> h a) -> k b -> Ran g h b

-- | <a>toRan</a> and <a>fromRan</a> witness a higher kinded adjunction.
--   from <tt>(`<tt>Compose'</tt> g)</tt> to <tt><a>Ran</a> g</tt>
--   
--   <pre>
--   <a>toRan</a> . <a>fromRan</a> ≡ <a>id</a>
--   <a>fromRan</a> . <a>toRan</a> ≡ <a>id</a>
--   </pre>
fromRan :: (forall a. k a -> Ran g h a) -> k (g b) -> h b

-- | This is the natural transformation that defines a Right Kan extension.
gran :: Ran g h (g a) -> h a

-- | <pre>
--   <a>composeRan</a> . <a>decomposeRan</a> ≡ <a>id</a>
--   <a>decomposeRan</a> . <a>composeRan</a> ≡ <a>id</a>
--   </pre>
composeRan :: Composition compose => Ran f (Ran g h) a -> Ran (compose f g) h a
decomposeRan :: (Composition compose, Functor f) => Ran (compose f g) h a -> Ran f (Ran g h) a

-- | <pre>
--   <a>adjointToRan</a> . <a>ranToAdjoint</a> ≡ <a>id</a>
--   <a>ranToAdjoint</a> . <a>adjointToRan</a> ≡ <a>id</a>
--   </pre>
adjointToRan :: Adjunction f g => f a -> Ran g Identity a
ranToAdjoint :: Adjunction f g => Ran g Identity a -> f a
composedAdjointToRan :: (Adjunction f g, Functor h) => h (f a) -> Ran g h a

-- | <pre>
--   <a>composedAdjointToRan</a> . <a>ranToComposedAdjoint</a> ≡ <a>id</a>
--   <a>ranToComposedAdjoint</a> . <a>composedAdjointToRan</a> ≡ <a>id</a>
--   </pre>
ranToComposedAdjoint :: Adjunction f g => Ran g h a -> h (f a)
repToRan :: Representable u => Rep u -> a -> Ran u Identity a
ranToRep :: Representable u => Ran u Identity a -> (Rep u, a)
composedRepToRan :: (Representable u, Functor h) => h (Rep u, a) -> Ran u h a
ranToComposedRep :: Representable u => Ran u h a -> h (Rep u, a)
instance GHC.Base.Functor (Data.Functor.Kan.Ran.Ran g h)


-- | The covariant form of the Yoneda lemma states that <tt>f</tt> is
--   naturally isomorphic to <tt>Yoneda f</tt>.
--   
--   This is described in a rather intuitive fashion by Dan Piponi in
--   
--   <a>http://blog.sigfpe.com/2006/11/yoneda-lemma.html</a>
module Data.Functor.Yoneda

-- | <tt>Yoneda f a</tt> can be viewed as the partial application of
--   <a>fmap</a> to its second argument.
newtype Yoneda f a
Yoneda :: (forall b. (a -> b) -> f b) -> Yoneda f a
[runYoneda] :: Yoneda f a -> forall b. (a -> b) -> f b

-- | The natural isomorphism between <tt>f</tt> and <tt><a>Yoneda</a>
--   f</tt> given by the Yoneda lemma is witnessed by <a>liftYoneda</a> and
--   <a>lowerYoneda</a>
--   
--   <pre>
--   <a>liftYoneda</a> . <a>lowerYoneda</a> ≡ <a>id</a>
--   <a>lowerYoneda</a> . <a>liftYoneda</a> ≡ <a>id</a>
--   </pre>
--   
--   <pre>
--   lowerYoneda (liftYoneda fa) =         -- definition
--   lowerYoneda (Yoneda (f -&gt; fmap f a)) -- definition
--   (f -&gt; fmap f fa) id                  -- beta reduction
--   fmap id fa                            -- functor law
--   fa
--   </pre>
--   
--   <pre>
--   <a>lift</a> = <a>liftYoneda</a>
--   </pre>
liftYoneda :: Functor f => f a -> Yoneda f a
lowerYoneda :: Yoneda f a -> f a
maxF :: (Functor f, Ord (f a)) => Yoneda f a -> Yoneda f a -> Yoneda f a
minF :: (Functor f, Ord (f a)) => Yoneda f a -> Yoneda f a -> Yoneda f a
maxM :: (Monad m, Ord (m a)) => Yoneda m a -> Yoneda m a -> Yoneda m a
minM :: (Monad m, Ord (m a)) => Yoneda m a -> Yoneda m a -> Yoneda m a

-- | <tt>Yoneda f</tt> can be viewed as the right Kan extension of
--   <tt>f</tt> along the <a>Identity</a> functor.
--   
--   <pre>
--   <a>yonedaToRan</a> . <a>ranToYoneda</a> ≡ <a>id</a>
--   <a>ranToYoneda</a> . <a>yonedaToRan</a> ≡ <a>id</a>
--   </pre>
yonedaToRan :: Yoneda f a -> Ran Identity f a
ranToYoneda :: Ran Identity f a -> Yoneda f a

-- | <tt>Yoneda f</tt> can be viewed as the right Kan lift of <tt>f</tt>
--   along the <a>Identity</a> functor.
--   
--   <pre>
--   <a>yonedaToRift</a> . <a>riftToYoneda</a> ≡ <a>id</a>
--   <a>riftToYoneda</a> . <a>yonedaToRift</a> ≡ <a>id</a>
--   </pre>
yonedaToRift :: Yoneda f a -> Rift Identity f a
riftToYoneda :: Rift Identity f a -> Yoneda f a
instance GHC.Base.Functor (Data.Functor.Yoneda.Yoneda f)
instance Data.Functor.Bind.Class.Apply f => Data.Functor.Bind.Class.Apply (Data.Functor.Yoneda.Yoneda f)
instance GHC.Base.Applicative f => GHC.Base.Applicative (Data.Functor.Yoneda.Yoneda f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Data.Functor.Yoneda.Yoneda f)
instance Data.Semigroup.Foldable.Class.Foldable1 f => Data.Semigroup.Foldable.Class.Foldable1 (Data.Functor.Yoneda.Yoneda f)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Data.Functor.Yoneda.Yoneda f)
instance Data.Semigroup.Traversable.Class.Traversable1 f => Data.Semigroup.Traversable.Class.Traversable1 (Data.Functor.Yoneda.Yoneda f)
instance Data.Distributive.Distributive f => Data.Distributive.Distributive (Data.Functor.Yoneda.Yoneda f)
instance Data.Functor.Rep.Representable g => Data.Functor.Rep.Representable (Data.Functor.Yoneda.Yoneda g)
instance Data.Functor.Adjunction.Adjunction f g => Data.Functor.Adjunction.Adjunction (Data.Functor.Yoneda.Yoneda f) (Data.Functor.Yoneda.Yoneda g)
instance GHC.Show.Show (f a) => GHC.Show.Show (Data.Functor.Yoneda.Yoneda f a)
instance (GHC.Base.Functor f, GHC.Read.Read (f a)) => GHC.Read.Read (Data.Functor.Yoneda.Yoneda f a)
instance GHC.Classes.Eq (f a) => GHC.Classes.Eq (Data.Functor.Yoneda.Yoneda f a)
instance GHC.Classes.Ord (f a) => GHC.Classes.Ord (Data.Functor.Yoneda.Yoneda f a)
instance Data.Functor.Alt.Alt f => Data.Functor.Alt.Alt (Data.Functor.Yoneda.Yoneda f)
instance Data.Functor.Plus.Plus f => Data.Functor.Plus.Plus (Data.Functor.Yoneda.Yoneda f)
instance GHC.Base.Alternative f => GHC.Base.Alternative (Data.Functor.Yoneda.Yoneda f)
instance Data.Functor.Bind.Class.Bind m => Data.Functor.Bind.Class.Bind (Data.Functor.Yoneda.Yoneda m)
instance GHC.Base.Monad m => GHC.Base.Monad (Data.Functor.Yoneda.Yoneda m)
instance Control.Monad.Fix.MonadFix m => Control.Monad.Fix.MonadFix (Data.Functor.Yoneda.Yoneda m)
instance GHC.Base.MonadPlus m => GHC.Base.MonadPlus (Data.Functor.Yoneda.Yoneda m)
instance Control.Monad.Trans.Class.MonadTrans Data.Functor.Yoneda.Yoneda
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Data.Functor.Yoneda.Yoneda m)
instance Data.Functor.Extend.Extend w => Data.Functor.Extend.Extend (Data.Functor.Yoneda.Yoneda w)
instance Control.Comonad.Comonad w => Control.Comonad.Comonad (Data.Functor.Yoneda.Yoneda w)
instance Control.Comonad.Trans.Class.ComonadTrans Data.Functor.Yoneda.Yoneda


module Control.Monad.Codensity

-- | <tt><a>Codensity</a> f</tt> is the Monad generated by taking the right
--   Kan extension of any <a>Functor</a> <tt>f</tt> along itself (<tt>Ran f
--   f</tt>).
--   
--   This can often be more "efficient" to construct than <tt>f</tt> itself
--   using repeated applications of <tt>(&gt;&gt;=)</tt>.
--   
--   See "Asymptotic Improvement of Computations over Free Monads" by Janis
--   Voightländer for more information about this type.
--   
--   <a>http://www.iai.uni-bonn.de/~jv/mpc08.pdf</a>
newtype Codensity m a
Codensity :: (forall b. (a -> m b) -> m b) -> Codensity m a
[runCodensity] :: Codensity m a -> forall b. (a -> m b) -> m b

-- | This serves as the *left*-inverse (retraction) of <a>lift</a>.
--   
--   <pre>
--   <a>lowerCodensity</a> . <a>lift</a> ≡ <a>id</a>
--   </pre>
--   
--   In general this is not a full 2-sided inverse, merely a retraction, as
--   <tt><a>Codensity</a> m</tt> is often considerably "larger" than
--   <tt>m</tt>.
--   
--   e.g. <tt><a>Codensity</a> ((-&gt;) s)) a ~ forall r. (a -&gt; s -&gt;
--   r) -&gt; s -&gt; r</tt> could support a full complement of
--   <tt><a>MonadState</a> s</tt> actions, while <tt>(-&gt;) s</tt> is
--   limited to <tt><a>MonadReader</a> s</tt> actions.
lowerCodensity :: Monad m => Codensity m a -> m a

-- | The <a>Codensity</a> monad of a right adjoint is isomorphic to the
--   monad obtained from the <a>Adjunction</a>.
--   
--   <pre>
--   <a>codensityToAdjunction</a> . <a>adjunctionToCodensity</a> ≡ <a>id</a>
--   <a>adjunctionToCodensity</a> . <a>codensityToAdjunction</a> ≡ <a>id</a>
--   </pre>
codensityToAdjunction :: Adjunction f g => Codensity g a -> g (f a)
adjunctionToCodensity :: Adjunction f g => g (f a) -> Codensity g a

-- | The <a>Codensity</a> <a>Monad</a> of a <a>Functor</a> <tt>g</tt> is
--   the right Kan extension (<a>Ran</a>) of <tt>g</tt> along itself.
--   
--   <pre>
--   <a>codensityToRan</a> . <a>ranToCodensity</a> ≡ <a>id</a>
--   <a>ranToCodensity</a> . <a>codensityToRan</a> ≡ <a>id</a>
--   </pre>
codensityToRan :: Codensity g a -> Ran g g a
ranToCodensity :: Ran g g a -> Codensity g a

-- | The <a>Codensity</a> monad of a representable <a>Functor</a> is
--   isomorphic to the monad obtained from the <a>Adjunction</a> for which
--   that <a>Functor</a> is the right adjoint.
--   
--   <pre>
--   <a>codensityToComposedRep</a> . <a>composedRepToCodensity</a> ≡ <a>id</a>
--   <a>composedRepToCodensity</a> . <a>codensityToComposedRep</a> ≡ <a>id</a>
--   </pre>
--   
--   <pre>
--   codensityToComposedRep = <a>ranToComposedRep</a> . <a>codensityToRan</a>
--   </pre>
codensityToComposedRep :: Representable u => Codensity u a -> u (Rep u, a)

-- | <pre>
--   <a>composedRepToCodensity</a> = <a>ranToCodensity</a> . <a>composedRepToRan</a>
--   </pre>
composedRepToCodensity :: Representable u => u (Rep u, a) -> Codensity u a

-- | Right associate all binds in a computation that generates a free monad
--   
--   This can improve the asymptotic efficiency of the result, while
--   preserving semantics.
--   
--   See "Asymptotic Improvement of Computations over Free Monads" by Janis
--   Voightländer for more information about this combinator.
--   
--   <a>http://www.iai.uni-bonn.de/~jv/mpc08.pdf</a>
improve :: Functor f => (forall m. MonadFree f m => m a) -> Free f a
instance GHC.Base.Functor (Control.Monad.Codensity.Codensity k)
instance Data.Functor.Bind.Class.Apply (Control.Monad.Codensity.Codensity f)
instance GHC.Base.Applicative (Control.Monad.Codensity.Codensity f)
instance GHC.Base.Monad (Control.Monad.Codensity.Codensity f)
instance Control.Monad.IO.Class.MonadIO m => Control.Monad.IO.Class.MonadIO (Control.Monad.Codensity.Codensity m)
instance Control.Monad.Trans.Class.MonadTrans Control.Monad.Codensity.Codensity
instance Data.Functor.Alt.Alt v => Data.Functor.Alt.Alt (Control.Monad.Codensity.Codensity v)
instance Data.Functor.Plus.Plus v => Data.Functor.Plus.Plus (Control.Monad.Codensity.Codensity v)
instance GHC.Base.Alternative v => GHC.Base.Alternative (Control.Monad.Codensity.Codensity v)
instance GHC.Base.MonadPlus v => GHC.Base.MonadPlus (Control.Monad.Codensity.Codensity v)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Codensity.Codensity m)
instance Control.Monad.Reader.Class.MonadReader r m => Control.Monad.State.Class.MonadState r (Control.Monad.Codensity.Codensity m)
instance Control.Monad.Reader.Class.MonadReader r m => Control.Monad.Reader.Class.MonadReader r (Control.Monad.Codensity.Codensity m)


-- | Left Kan Extensions
module Data.Functor.Kan.Lan

-- | The left Kan extension of a <a>Functor</a> <tt>h</tt> along a
--   <a>Functor</a> <tt>g</tt>.
data Lan g h a
Lan :: (g b -> a) -> h b -> Lan g h a

-- | The universal property of a left Kan extension.
toLan :: Functor f => (forall a. h a -> f (g a)) -> Lan g h b -> f b

-- | <a>fromLan</a> and <a>toLan</a> witness a (higher kinded) adjunction
--   between <tt><a>Lan</a> g</tt> and <tt>(<tt>Compose</tt> g)</tt>
--   
--   <pre>
--   <a>toLan</a> . <a>fromLan</a> ≡ <a>id</a>
--   <a>fromLan</a> . <a>toLan</a> ≡ <a>id</a>
--   </pre>
fromLan :: (forall a. Lan g h a -> f a) -> h b -> f (g b)

-- | This is the natural transformation that defines a Left Kan extension.
glan :: h a -> Lan g h (g a)

-- | <a>composeLan</a> and <a>decomposeLan</a> witness the natural
--   isomorphism from <tt>Lan f (Lan g h)</tt> and <tt>Lan (f <tt>o</tt> g)
--   h</tt>
--   
--   <pre>
--   <a>composeLan</a> . <a>decomposeLan</a> ≡ <a>id</a>
--   <a>decomposeLan</a> . <a>composeLan</a> ≡ <a>id</a>
--   </pre>
composeLan :: (Composition compose, Functor f) => Lan f (Lan g h) a -> Lan (compose f g) h a
decomposeLan :: Composition compose => Lan (compose f g) h a -> Lan f (Lan g h) a

-- | <pre>
--   <a>adjointToLan</a> . <a>lanToAdjoint</a> ≡ <a>id</a>
--   <a>lanToAdjoint</a> . <a>adjointToLan</a> ≡ <a>id</a>
--   </pre>
adjointToLan :: Adjunction f g => g a -> Lan f Identity a
lanToAdjoint :: Adjunction f g => Lan f Identity a -> g a
composedAdjointToLan :: Adjunction f g => h (g a) -> Lan f h a

-- | <a>lanToComposedAdjoint</a> and <a>composedAdjointToLan</a> witness
--   the natural isomorphism between <tt>Lan f h</tt> and <tt>Compose h
--   g</tt> given <tt>f -| g</tt>
--   
--   <pre>
--   <a>composedAdjointToLan</a> . <a>lanToComposedAdjoint</a> ≡ <a>id</a>
--   <a>lanToComposedAdjoint</a> . <a>composedAdjointToLan</a> ≡ <a>id</a>
--   </pre>
lanToComposedAdjoint :: (Functor h, Adjunction f g) => Lan f h a -> h (g a)
instance GHC.Base.Functor (Data.Functor.Kan.Lan.Lan f g)
instance (GHC.Base.Functor g, Data.Functor.Bind.Class.Apply h) => Data.Functor.Bind.Class.Apply (Data.Functor.Kan.Lan.Lan g h)
instance (GHC.Base.Functor g, GHC.Base.Applicative h) => GHC.Base.Applicative (Data.Functor.Kan.Lan.Lan g h)


-- | The co-Yoneda lemma for a covariant <a>Functor</a> <tt>f</tt> states
--   that <tt><a>Coyoneda</a> f</tt> is naturally isomorphic to <tt>f</tt>.
module Data.Functor.Coyoneda

-- | A covariant <a>Functor</a> suitable for Yoneda reduction
data Coyoneda f a
Coyoneda :: (b -> a) -> f b -> Coyoneda f a

-- | Yoneda "expansion"
--   
--   <pre>
--   <a>liftCoyoneda</a> . <a>lowerCoyoneda</a> ≡ <a>id</a>
--   <a>lowerCoyoneda</a> . <a>liftCoyoneda</a> ≡ <a>id</a>
--   </pre>
--   
--   <pre>
--   lowerCoyoneda (liftCoyoneda fa) = -- by definition
--   lowerCoyoneda (Coyoneda id fa)  = -- by definition
--   fmap id fa                      = -- functor law
--   fa
--   </pre>
--   
--   <pre>
--   <a>lift</a> = <a>liftCoyoneda</a>
--   </pre>
liftCoyoneda :: f a -> Coyoneda f a

-- | Yoneda reduction lets us walk under the existential and apply
--   <a>fmap</a>.
--   
--   Mnemonically, "Yoneda reduction" sounds like and works a bit like
--   β-reduction.
--   
--   <a>http://ncatlab.org/nlab/show/Yoneda+reduction</a>
--   
--   You can view <a>Coyoneda</a> as just the arguments to <a>fmap</a>
--   tupled up.
--   
--   <pre>
--   <a>lower</a> = <a>lowerM</a> = <a>lowerCoyoneda</a>
--   </pre>
lowerCoyoneda :: Functor f => Coyoneda f a -> f a

-- | Yoneda reduction given a <a>Monad</a> lets us walk under the
--   existential and apply <a>liftM</a>.
--   
--   You can view <a>Coyoneda</a> as just the arguments to <a>liftM</a>
--   tupled up.
--   
--   <pre>
--   <a>lower</a> = <a>lowerM</a> = <a>lowerCoyoneda</a>
--   </pre>
lowerM :: Monad f => Coyoneda f a -> f a

-- | <tt>Coyoneda f</tt> is the left Kan extension of <tt>f</tt> along the
--   <a>Identity</a> functor.
--   
--   <pre>
--   <a>coyonedaToLan</a> . <a>lanToCoyoneda</a> ≡ <a>id</a>
--   <a>lanToCoyoneda</a> . <a>coyonedaToLan</a> ≡ <a>id</a>
--   </pre>
coyonedaToLan :: Coyoneda f a -> Lan Identity f a
lanToCoyoneda :: Lan Identity f a -> Coyoneda f a

-- | <tt><a>Coyoneda</a> f</tt> is the left Kan lift of <tt>f</tt> along
--   the <a>Identity</a> functor.
--   
--   <pre>
--   <a>coyonedaToLift</a> . <a>liftToCoyoneda</a> ≡ <a>id</a>
--   <a>liftToCoyoneda</a> . <a>coyonedaToLift</a> ≡ <a>id</a>
--   </pre>
coyonedaToLift :: Coyoneda f a -> Lift Identity f a
liftToCoyoneda :: Functor f => Lift Identity f a -> Coyoneda f a
instance GHC.Base.Functor (Data.Functor.Coyoneda.Coyoneda f)
instance Data.Functor.Bind.Class.Apply f => Data.Functor.Bind.Class.Apply (Data.Functor.Coyoneda.Coyoneda f)
instance GHC.Base.Applicative f => GHC.Base.Applicative (Data.Functor.Coyoneda.Coyoneda f)
instance GHC.Base.Alternative f => GHC.Base.Alternative (Data.Functor.Coyoneda.Coyoneda f)
instance Data.Functor.Alt.Alt f => Data.Functor.Alt.Alt (Data.Functor.Coyoneda.Coyoneda f)
instance Data.Functor.Plus.Plus f => Data.Functor.Plus.Plus (Data.Functor.Coyoneda.Coyoneda f)
instance Data.Functor.Bind.Class.Bind m => Data.Functor.Bind.Class.Bind (Data.Functor.Coyoneda.Coyoneda m)
instance GHC.Base.Monad m => GHC.Base.Monad (Data.Functor.Coyoneda.Coyoneda m)
instance Control.Monad.Trans.Class.MonadTrans Data.Functor.Coyoneda.Coyoneda
instance Control.Monad.Fix.MonadFix f => Control.Monad.Fix.MonadFix (Data.Functor.Coyoneda.Coyoneda f)
instance GHC.Base.MonadPlus f => GHC.Base.MonadPlus (Data.Functor.Coyoneda.Coyoneda f)
instance Data.Functor.Rep.Representable f => Data.Functor.Rep.Representable (Data.Functor.Coyoneda.Coyoneda f)
instance Data.Functor.Extend.Extend w => Data.Functor.Extend.Extend (Data.Functor.Coyoneda.Coyoneda w)
instance Control.Comonad.Comonad w => Control.Comonad.Comonad (Data.Functor.Coyoneda.Coyoneda w)
instance Control.Comonad.Trans.Class.ComonadTrans Data.Functor.Coyoneda.Coyoneda
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Data.Functor.Coyoneda.Coyoneda f)
instance Data.Semigroup.Foldable.Class.Foldable1 f => Data.Semigroup.Foldable.Class.Foldable1 (Data.Functor.Coyoneda.Coyoneda f)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Data.Functor.Coyoneda.Coyoneda f)
instance Data.Semigroup.Traversable.Class.Traversable1 f => Data.Semigroup.Traversable.Class.Traversable1 (Data.Functor.Coyoneda.Coyoneda f)
instance Data.Distributive.Distributive f => Data.Distributive.Distributive (Data.Functor.Coyoneda.Coyoneda f)
instance (GHC.Base.Functor f, GHC.Show.Show (f a)) => GHC.Show.Show (Data.Functor.Coyoneda.Coyoneda f a)
instance (GHC.Base.Functor f, GHC.Read.Read (f a)) => GHC.Read.Read (Data.Functor.Coyoneda.Coyoneda f a)
instance (GHC.Base.Functor f, GHC.Classes.Eq (f a)) => GHC.Classes.Eq (Data.Functor.Coyoneda.Coyoneda f a)
instance (GHC.Base.Functor f, GHC.Classes.Ord (f a)) => GHC.Classes.Ord (Data.Functor.Coyoneda.Coyoneda f a)
instance Data.Functor.Adjunction.Adjunction f g => Data.Functor.Adjunction.Adjunction (Data.Functor.Coyoneda.Coyoneda f) (Data.Functor.Coyoneda.Coyoneda g)


-- | The <a>Density</a> <a>Comonad</a> for a <a>Functor</a> (aka the
--   'Comonad generated by a <a>Functor</a>) The <a>Density</a> term dates
--   back to Dubuc''s 1974 thesis. The term <a>Monad</a> genererated by a
--   <a>Functor</a> dates back to 1972 in Street''s ''Formal Theory of
--   Monads''.
--   
--   The left Kan extension of a <a>Functor</a> along itself
--   (<tt><a>Lan</a> f f</tt>) forms a <a>Comonad</a>. This is that
--   <a>Comonad</a>.
module Control.Comonad.Density
data Density k a
Density :: (k b -> a) -> k b -> Density k a

-- | The natural transformation from a <tt><a>Comonad</a> w</tt> to the
--   <a>Comonad</a> generated by <tt>w</tt> (forwards).
--   
--   This is merely a right-inverse (section) of <a>lower</a>, rather than
--   a full inverse.
--   
--   <pre>
--   <a>lower</a> . <a>liftDensity</a> ≡ <a>id</a>
--   </pre>
liftDensity :: Comonad w => w a -> Density w a

-- | The Density <a>Comonad</a> of a left adjoint is isomorphic to the
--   <a>Comonad</a> formed by that <a>Adjunction</a>.
--   
--   This isomorphism is witnessed by <a>densityToAdjunction</a> and
--   <a>adjunctionToDensity</a>.
--   
--   <pre>
--   <a>densityToAdjunction</a> . <a>adjunctionToDensity</a> ≡ <a>id</a>
--   <a>adjunctionToDensity</a> . <a>densityToAdjunction</a> ≡ <a>id</a>
--   </pre>
densityToAdjunction :: Adjunction f g => Density f a -> f (g a)
adjunctionToDensity :: Adjunction f g => f (g a) -> Density f a
densityToLan :: Density f a -> Lan f f a

-- | The <a>Density</a> <a>Comonad</a> of a <a>Functor</a> <tt>f</tt> is
--   obtained by taking the left Kan extension (<a>Lan</a>) of <tt>f</tt>
--   along itself. This isomorphism is witnessed by <a>lanToDensity</a> and
--   <a>densityToLan</a>
--   
--   <pre>
--   <a>lanToDensity</a> . <a>densityToLan</a> ≡ <a>id</a>
--   <a>densityToLan</a> . <a>lanToDensity</a> ≡ <a>id</a>
--   </pre>
lanToDensity :: Lan f f a -> Density f a
instance GHC.Base.Functor (Control.Comonad.Density.Density f)
instance Data.Functor.Extend.Extend (Control.Comonad.Density.Density f)
instance Control.Comonad.Comonad (Control.Comonad.Density.Density f)
instance Control.Comonad.Trans.Class.ComonadTrans Control.Comonad.Density.Density
instance Data.Functor.Bind.Class.Apply f => Data.Functor.Bind.Class.Apply (Control.Comonad.Density.Density f)
instance GHC.Base.Applicative f => GHC.Base.Applicative (Control.Comonad.Density.Density f)


-- | Monads from Comonads
--   
--   <a>http://comonad.com/reader/2011/monads-from-comonads/</a>
--   
--   <a>Co</a> can be viewed as a right Kan lift along a <a>Comonad</a>.
--   
--   In general you can "sandwich" a monad in between two halves of an
--   adjunction. That is to say, if you have an adjunction <tt>F -| G : C
--   -&gt; D </tt> then not only does <tt>GF</tt> form a monad, but
--   <tt>GMF</tt> forms a monad for <tt>M</tt> a monad in <tt>D</tt>.
--   Therefore if we have an adjunction <tt>F -| G : Hask -&gt;
--   Hask^op</tt> then we can lift a <a>Comonad</a> in <tt>Hask</tt> which
--   is a <a>Monad</a> in <tt>Hask^op</tt> to a <a>Monad</a> in
--   <tt>Hask</tt>.
--   
--   For any <tt>r</tt>, the <tt>Contravariant</tt> functor / presheaf
--   <tt>(-&gt; r)</tt> :: Hask^op -&gt; Hask is adjoint to the "same"
--   <tt>Contravariant</tt> functor <tt>(-&gt; r) :: Hask -&gt;
--   Hask^op</tt>. So we can sandwhich a Monad in Hask^op in the middle to
--   obtain <tt>w (a -&gt; r-) -&gt; r+</tt>, and then take a coend over
--   <tt>r</tt> to obtain <tt>forall r. w (a -&gt; r) -&gt; r</tt>. This
--   gives rise to <a>Co</a>. If we observe that we didn't care what the
--   choices we made for <tt>r</tt> were to finish this construction, we
--   can upgrade to <tt>forall r. w (a -&gt; m r) -&gt; m r</tt> in a
--   manner similar to how <tt>ContT</tt> is constructed yielding
--   <a>CoT</a>.
--   
--   We could consider unifying the definition of <a>Co</a> and
--   <tt>Rift</tt>, but there are many other arguments for which
--   <tt>Rift</tt> can form a <a>Monad</a>, and this wouldn't give rise to
--   <a>CoT</a>.
module Control.Monad.Co
type Co w = CoT w Identity
co :: Functor w => (forall r. w (a -> r) -> r) -> Co w a
runCo :: Functor w => Co w a -> w (a -> r) -> r

-- | <pre>
--   <a>Co</a> w a ~ <a>Rift</a> w <a>Identity</a> a
--   </pre>
newtype CoT w m a
CoT :: (forall r. w (a -> m r) -> m r) -> CoT w m a
[runCoT] :: CoT w m a -> forall r. w (a -> m r) -> m r
liftCoT0 :: Comonad w => (forall a. w a -> s) -> CoT w m s
liftCoT0M :: (Comonad w, Monad m) => (forall a. w a -> m s) -> CoT w m s
lowerCoT0 :: (Functor w, Monad m) => CoT w m s -> w a -> m s
lowerCo0 :: Functor w => Co w s -> w a -> s
liftCoT1 :: (forall a. w a -> a) -> CoT w m ()
liftCoT1M :: Monad m => (forall a. w a -> m a) -> CoT w m ()
lowerCoT1 :: (Functor w, Monad m) => CoT w m () -> w a -> m a
lowerCo1 :: Functor w => Co w () -> w a -> a
diter :: Functor f => a -> (a -> f a) -> Density (Cofree f) a
dctrlM :: (Comonad w, Monad m) => (forall a. w a -> m (w a)) -> CoT (Density w) m ()
posW :: (ComonadStore s w, Monad m) => CoT w m s
peekW :: (ComonadStore s w, Monad m) => s -> CoT w m ()
peeksW :: (ComonadStore s w, Monad m) => (s -> s) -> CoT w m ()
askW :: (ComonadEnv e w, Monad m) => CoT w m e
asksW :: (ComonadEnv e w, Monad m) => (e -> a) -> CoT w m a
traceW :: (ComonadTraced e w, Monad m) => e -> CoT w m ()
instance GHC.Base.Functor w => GHC.Base.Functor (Control.Monad.Co.CoT w m)
instance Data.Functor.Extend.Extend w => Data.Functor.Bind.Class.Apply (Control.Monad.Co.CoT w m)
instance Data.Functor.Extend.Extend w => Data.Functor.Bind.Class.Bind (Control.Monad.Co.CoT w m)
instance Control.Comonad.Comonad w => GHC.Base.Applicative (Control.Monad.Co.CoT w m)
instance Control.Comonad.Comonad w => GHC.Base.Monad (Control.Monad.Co.CoT w m)
instance Control.Comonad.Comonad w => Control.Monad.Trans.Class.MonadTrans (Control.Monad.Co.CoT w)
instance (Control.Comonad.Comonad w, Control.Monad.IO.Class.MonadIO m) => Control.Monad.IO.Class.MonadIO (Control.Monad.Co.CoT w m)
instance (Control.Comonad.Comonad w, Control.Monad.Reader.Class.MonadReader e m) => Control.Monad.Reader.Class.MonadReader e (Control.Monad.Co.CoT w m)
instance (Control.Comonad.Comonad w, Control.Monad.State.Class.MonadState s m) => Control.Monad.State.Class.MonadState s (Control.Monad.Co.CoT w m)
instance (Control.Comonad.Comonad w, Control.Monad.Writer.Class.MonadWriter e m) => Control.Monad.Writer.Class.MonadWriter e (Control.Monad.Co.CoT w m)
instance (Control.Comonad.Comonad w, Control.Monad.Error.Class.MonadError e m) => Control.Monad.Error.Class.MonadError e (Control.Monad.Co.CoT w m)
