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

--   g . Rift g f => f
--

-- -- This could alternately be defined directly from the (co)universal -- propertly in which case, we'd get toRift = -- UniversalRift, but then the usage would suffer. -- --

--   data UniversalRift g f a = forall z. Functor z =>
--        UniversalRift (forall x. g (z x) -> f x) (z a)
--

-- -- We can witness the isomorphism between Rift and UniversalRift using: -- --

--   riftIso1 :: Functor g => UniversalRift g f a -> Rift g f a
--   riftIso1 (UniversalRift h z) = Rift $ \g -> h $ fmap (\k -> k <$> z) g
--

-- --

--   riftIso2 :: Rift g f a -> UniversalRift g f a
--   riftIso2 (Rift e) = UniversalRift e id
--

-- --

--   riftIso1 (riftIso2 (Rift h)) =
--   riftIso1 (UniversalRift h id) =          -- by definition
--   Rift $ \g -> h $ fmap (\k -> k <$> id) g -- by definition
--   Rift $ \g -> h $ fmap id g               -- <$> = (.) and (.id)
--   Rift $ \g -> h g                         -- by functor law
--   Rift h                                   -- eta reduction
--

-- -- The other direction is left as an exercise for the reader. -- -- There are several monads that we can form from Rift. -- -- When g is corepresentable (e.g. is a right adjoint) then -- there exists x such that g ~ (->) x, then it -- follows that -- --

--   Rift g g a ~
--   forall r. (x -> a -> r) -> x -> r ~
--   forall r. (a -> x -> r) -> x -> r ~
--   forall r. (a -> g r) -> g r ~
--   Codensity g r
--

-- -- When f is a left adjoint, so that f -| g then -- --

--   Rift f f a ~
--   forall r. f (a -> r) -> f r ~
--   forall r. (a -> r) -> g (f r) ~
--   forall r. (a -> r) -> Adjoint f g r ~
--   Yoneda (Adjoint f g r)
--

-- -- An alternative way to view that is to note that whenever f is -- a left adjoint then f -| Rift f Identity, and -- since Rift f f is isomorphic to Rift f -- Identity (f a), this is the Monad formed by the -- adjunction. -- -- Rift Identity m can be a Monad for any -- Monad m, as it is isomorphic to Yoneda -- m. 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 Rift toRift :: (Functor g, Functor k) => (forall x. g (k x) -> h x) -> k a -> Rift g h a -- | When f -| u, then f -| Rift f Identity and -- --

--   toRift . fromRift ≡ id
--   fromRift . toRift ≡ id
--

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

--   composeRift . decomposeRift ≡ id
--   decomposeRift . composeRift ≡ id
--

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 -- | Rift f Identity a is isomorphic to the right adjoint to -- f if one exists. -- --

--   adjointToRift . riftToAdjoint ≡ id
--   riftToAdjoint . adjointToRift ≡ id
--

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

--   riftToComposedAdjoint . composedAdjointToRift ≡ id
--   composedAdjointToRift . riftToComposedAdjoint ≡ id
--

riftToComposedAdjoint :: Adjunction f u => Rift f h a -> u (h 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 (Functor g, g ~ h) => Applicative (Rift g h) instance Functor g => Functor (Rift g h) -- | Left Kan lifts for functors over Hask, wherever they exist. -- -- http://ncatlab.org/nlab/show/Kan+lift module Data.Functor.Kan.Lift -- |

--   f => g . Lift g f
--   (forall z. f => g . z) -> Lift g f => z -- couniversal
--

-- -- Here we use the universal property directly as how we extract from our -- definition of Lift. 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 Lift toLift :: Functor z => (forall a. f a -> g (z a)) -> Lift g f b -> z b -- | When the adjunction exists -- --

--   fromLift . toLift ≡ id
--   toLift . fromLift ≡ id
--

fromLift :: Adjunction l u => (forall a. Lift u f a -> z a) -> f b -> u (z b) -- |

--   f => g (Lift g f a)
--

glift :: Adjunction l g => k a -> g (Lift g k a) -- |

--   composeLift . decomposeLift = id
--   decomposeLift . composeLift = id
--

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 -- | Lift u Identity a is isomorphic to the left adjoint to -- u if one exists. -- --

--   adjointToLift . liftToAdjoint ≡ id
--   liftToAdjoint . adjointToLift ≡ id
--

adjointToLift :: Adjunction f u => f a -> Lift u Identity a -- | Lift u Identity a is isomorphic to the left adjoint to -- u if one exists. liftToAdjoint :: Adjunction f u => Lift u Identity a -> f a -- | Lift u h a is isomorphic to the post-composition of the left -- adjoint of u onto h if such a left adjoint exists. -- --

--   liftToComposedAdjoint . composedAdjointToLift ≡ id
--   composedAdjointToLift . liftToComposedAdjoint ≡ id
--

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

--   repToLift . liftToRep ≡ id
--   liftToRep . repToLift ≡ id
--

repToLift :: Representable u => Rep u -> a -> Lift u Identity a liftToRep :: Representable u => Lift u Identity a -> (Rep u, a) -- |

--   liftToComposedRep . composedRepToLift ≡ id
--   composedRepToLift . liftToComposedRep ≡ id
--

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 Functor (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. -- -- http://ncatlab.org/nlab/show/Day+convolution module Data.Functor.Day -- | The Day convolution of two covariant functors. -- -- Day f g a -> h a is isomorphic to f a -> Rift g h -- a 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. -- --

--   dap (day f g) = f <*> g
--

dap :: Applicative f => Day f f a -> f a -- | Day convolution provides a monoidal product. The associativity of this -- monoid is witnessed by assoc and disassoc. -- --

--   assoc . disassoc = id
--   disassoc . assoc = id
--   fmap f . assoc = assoc . fmap f
--

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 assoc and disassoc. -- --

--   assoc . disassoc = id
--   disassoc . assoc = id
--   fmap f . disassoc = disassoc . fmap f
--

disassoc :: Day (Day f g) h a -> Day f (Day g h) a -- | The monoid for Day convolution on the cartesian monoidal -- structure is symmetric. -- --

--   fmap f . swapped = swapped . fmap f
--

swapped :: Day f g a -> Day g f a -- | Identity is the unit of Day convolution -- --

--   intro1 . elim1 = id
--   elim1 . intro1 = id
--

intro1 :: f a -> Day Identity f a -- | Identity is the unit of Day convolution -- --

--   intro2 . elim2 = id
--   elim2 . intro2 = id
--

intro2 :: f a -> Day f Identity a -- | Identity is the unit of Day convolution -- --

--   intro1 . elim1 = id
--   elim1 . intro1 = id
--

elim1 :: Functor f => Day Identity f a -> f a -- | Identity is the unit of Day convolution -- --

--   intro2 . elim2 = id
--   elim2 . intro2 = id
--

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

--   fmap f . trans1 fg = trans1 fg . fmap f
--

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

--   fmap f . trans2 fg = trans2 fg . fmap f
--

trans2 :: (forall x. g x -> h x) -> Day f g a -> Day f h a instance Typeable Day instance (Representable f, Representable g) => Representable (Day f g) instance (Representable f, Representable g) => Distributive (Day f g) instance (Applicative f, Applicative g) => Applicative (Day f g) instance Functor (Day f g) -- | The co-Yoneda lemma for presheafs states that f is naturally -- isomorphic to Coyoneda f. module Data.Functor.Contravariant.Coyoneda -- | A Contravariant functor (aka presheaf) suitable for Yoneda -- reduction. -- -- http://ncatlab.org/nlab/show/Yoneda+reduction data Coyoneda f a Coyoneda :: (a -> b) -> f b -> Coyoneda f a -- | Coyoneda "expansion" of a presheaf -- --

--   liftCoyoneda . lowerCoyoneda ≡ id
--   lowerCoyoneda . liftCoyoneda ≡ id
--

liftCoyoneda :: f a -> Coyoneda f a -- | Coyoneda reduction on a presheaf lowerCoyoneda :: Contravariant f => Coyoneda f a -> f a instance Adjunction f g => Adjunction (Coyoneda f) (Coyoneda g) instance Representable f => Representable (Coyoneda f) instance Contravariant (Coyoneda f) 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 -- |

--   liftYoneda . lowerYoneda ≡ id
--   lowerYoneda . liftYoneda ≡ id
--

liftYoneda :: Contravariant f => f a -> Yoneda f a lowerYoneda :: Yoneda f a -> f a instance Adjunction f g => Adjunction (Yoneda f) (Yoneda g) instance Representable f => Representable (Yoneda f) instance Contravariant (Yoneda f) -- | The Day convolution of two contravariant functors is a contravariant -- functor. -- -- http://ncatlab.org/nlab/show/Day+convolution 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 -- --

--   day1 (day f g) = f
--   day2 (day f g) = g
--

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 assoc and disassoc. -- --

--   assoc . disassoc = id
--   disassoc . assoc = id
--   contramap f . assoc = assoc . contramap f
--

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 assoc and disassoc. -- --

--   assoc . disassoc = id
--   disassoc . assoc = id
--   contramap f . disassoc = disassoc . contramap f
--

disassoc :: Day (Day f g) h a -> Day f (Day g h) a -- | The monoid for Day convolution in Haskell is symmetric. -- --

--   contramap f . swapped = swapped . contramap f
--

swapped :: Day f g a -> Day g f a -- | Proxy serves as the unit of Day convolution. -- --

--   day1 . intro1 = id
--   contramap f . intro1 = intro1 . contramap f
--

intro1 :: f a -> Day Proxy f a -- | Proxy serves as the unit of Day convolution. -- --

--   day2 . intro2 = id
--   contramap f . intro2 = intro2 . contramap f
--

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

--   day1 . intro1 = id
--   day1 = fst . runDay
--   contramap f . day1 = day1 . contramap f
--

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. -- day2 . intro2 = id day2 = -- snd . runDay contramap f . -- day2 = day2 . contramap f day2 :: Contravariant g => Day f g a -> g a -- | Diagonalize the Day convolution: -- --

--   day1 . diag = id
--   day2 . diag = id
--   runDay . diag = a -> (a,a)
--   contramap f . diag = diag . contramap f
--

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

--   contramap f . trans1 fg = trans1 fg . contramap f
--

--   contramap f . trans2 fg = trans2 fg . contramap f
--

trans2 :: (forall x. g x -> h x) -> Day f g a -> Day f h a instance Typeable Day instance (Representable f, Representable g) => Representable (Day f g) instance Contravariant (Day f g) -- |

Right Kan Extensions

module Data.Functor.Kan.Ran -- | The right Kan extension of a Functor h along a Functor -- 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 Functor h : C -> D and a Functor -- g : C -> C', we want to find extend h back -- along g to give Ran g h : C' -> C, such that the -- natural transformation gran :: 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! -- --

--   Hask -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' -> C such that we have a -- natural transformation from k.g to h (forall x. -- k (g x) -> h x) there exists a canonical natural -- transformation from k to Ran g h. (forall x. k x -- -> Ran g h x). -- -- We could literally read this off as a valid Rank-3 definition for -- Ran: -- --

--   data Ran' g h a = forall z. Functor 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
--

-- --

--   ranIso2 :: Ran' g f x -> Ran g f x
--   ranIso2 (Ran' h z) = Ran $ \k -> h (k <$> z)
--

-- --

--   ranIso2 (ranIso1 (Ran e)) ≡ -- by definition
--   ranIso2 (Ran' e id) ≡       -- 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. 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 -- | toRan and fromRan witness a higher kinded adjunction. -- from (`'Compose'` g) to Ran g -- --

--   toRan . fromRan ≡ id
--   fromRan . toRan ≡ id
--

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

--   composeRan . decomposeRan ≡ id
--   decomposeRan . composeRan ≡ id
--

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

--   adjointToRan . ranToAdjoint ≡ id
--   ranToAdjoint . adjointToRan ≡ id
--

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

--   composedAdjointToRan . ranToComposedAdjoint ≡ id
--   ranToComposedAdjoint . composedAdjointToRan ≡ id
--

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 Functor (Ran g h) -- | The covariant form of the Yoneda lemma states that f is -- naturally isomorphic to Yoneda f. -- -- This is described in a rather intuitive fashion by Dan Piponi in -- -- http://blog.sigfpe.com/2006/11/yoneda-lemma.html module Data.Functor.Yoneda -- | Yoneda f a can be viewed as the partial application of -- fmap 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 f and Yoneda -- f given by the Yoneda lemma is witnessed by liftYoneda and -- lowerYoneda -- --

--   liftYoneda . lowerYoneda ≡ id
--   lowerYoneda . liftYoneda ≡ id
--

-- --

--   lowerYoneda (liftYoneda fa) =         -- definition
--   lowerYoneda (Yoneda (f -> fmap f a)) -- definition
--   (f -> fmap f fa) id                  -- beta reduction
--   fmap id fa                            -- functor law
--   fa
--

-- --

--   lift = liftYoneda
--

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 -- | Yoneda f can be viewed as the right Kan extension of -- f along the Identity functor. -- --

--   yonedaToRan . ranToYoneda ≡ id
--   ranToYoneda . yonedaToRan ≡ id
--

yonedaToRan :: Yoneda f a -> Ran Identity f a ranToYoneda :: Ran Identity f a -> Yoneda f a -- | Yoneda f can be viewed as the right Kan lift of f -- along the Identity functor. -- --

--   yonedaToRift . riftToYoneda ≡ id
--   riftToYoneda . yonedaToRift ≡ id
--

yonedaToRift :: Yoneda f a -> Rift Identity f a riftToYoneda :: Rift Identity f a -> Yoneda f a instance ComonadTrans Yoneda instance Comonad w => Comonad (Yoneda w) instance Extend w => Extend (Yoneda w) instance (Functor f, MonadFree f m) => MonadFree f (Yoneda m) instance MonadTrans Yoneda instance MonadPlus m => MonadPlus (Yoneda m) instance MonadFix m => MonadFix (Yoneda m) instance Monad m => Monad (Yoneda m) instance Bind m => Bind (Yoneda m) instance Alternative f => Alternative (Yoneda f) instance Plus f => Plus (Yoneda f) instance Alt f => Alt (Yoneda f) instance Ord (f a) => Ord (Yoneda f a) instance Eq (f a) => Eq (Yoneda f a) instance (Functor f, Read (f a)) => Read (Yoneda f a) instance Show (f a) => Show (Yoneda f a) instance Adjunction f g => Adjunction (Yoneda f) (Yoneda g) instance Representable g => Representable (Yoneda g) instance Distributive f => Distributive (Yoneda f) instance Traversable1 f => Traversable1 (Yoneda f) instance Traversable f => Traversable (Yoneda f) instance Foldable1 f => Foldable1 (Yoneda f) instance Foldable f => Foldable (Yoneda f) instance Applicative f => Applicative (Yoneda f) instance Apply f => Apply (Yoneda f) instance Functor (Yoneda f) module Control.Monad.Codensity -- | Codensity f is the Monad generated by taking the right -- Kan extension of any Functor f along itself (Ran f -- f). -- -- This can often be more "efficient" to construct than f itself -- using repeated applications of (>>=). -- -- See "Asymptotic Improvement of Computations over Free Monads" by Janis -- Voightländer for more information about this type. -- -- http://www.iai.uni-bonn.de/~jv/mpc08.pdf 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 lift. -- --

--   lowerCodensity . lift ≡ id
--

-- -- In general this is not a full 2-sided inverse, merely a retraction, as -- Codensity m is often considerably "larger" than -- m. -- -- e.g. Codensity ((->) s)) a ~ forall r. (a -> s -> -- r) -> s -> r could support a full complement of -- MonadState s actions, while (->) s is -- limited to MonadReader s actions. lowerCodensity :: Monad m => Codensity m a -> m a -- | The Codensity monad of a right adjoint is isomorphic to the -- monad obtained from the Adjunction. -- --

--   codensityToAdjunction . adjunctionToCodensity ≡ id
--   adjunctionToCodensity . codensityToAdjunction ≡ id
--

codensityToAdjunction :: Adjunction f g => Codensity g a -> g (f a) adjunctionToCodensity :: Adjunction f g => g (f a) -> Codensity g a -- | The Codensity Monad of a Functor g is -- the right Kan extension (Ran) of g along itself. -- --

--   codensityToRan . ranToCodensity ≡ id
--   ranToCodensity . codensityToRan ≡ id
--

codensityToRan :: Codensity g a -> Ran g g a ranToCodensity :: Ran g g a -> Codensity g a -- | The Codensity monad of a representable Functor is -- isomorphic to the monad obtained from the Adjunction for which -- that Functor is the right adjoint. -- --

--   codensityToComposedRep . composedRepToCodensity ≡ id
--   composedRepToCodensity . codensityToComposedRep ≡ id
--

-- --

--   codensityToComposedRep = ranToComposedRep . codensityToRan
--

codensityToComposedRep :: Representable u => Codensity u a -> u (Rep u, a) -- |

--   composedRepToCodensity = ranToCodensity . composedRepToRan
--

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. -- -- http://www.iai.uni-bonn.de/~jv/mpc08.pdf improve :: Functor f => (forall m. MonadFree f m => m a) -> Free f a instance Typeable Codensity instance MonadReader r m => MonadReader r (Codensity m) instance MonadReader r m => MonadState r (Codensity m) instance (Functor f, MonadFree f m) => MonadFree f (Codensity m) instance MonadPlus v => MonadPlus (Codensity v) instance Alternative v => Alternative (Codensity v) instance Plus v => Plus (Codensity v) instance Alt v => Alt (Codensity v) instance MonadTrans Codensity instance MonadIO m => MonadIO (Codensity m) instance Monad (Codensity f) instance Applicative (Codensity f) instance Apply (Codensity f) instance Functor (Codensity k) -- | Left Kan Extensions module Data.Functor.Kan.Lan -- | The left Kan extension of a Functor h along a -- Functor g. 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 -- | fromLan and toLan witness a (higher kinded) adjunction -- between Lan g and (Compose g) -- --

--   toLan . fromLan ≡ id
--   fromLan . toLan ≡ id
--

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) -- | composeLan and decomposeLan witness the natural -- isomorphism from Lan f (Lan g h) and Lan (f o g) -- h -- --

--   composeLan . decomposeLan ≡ id
--   decomposeLan . composeLan ≡ id
--

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

--   adjointToLan . lanToAdjoint ≡ id
--   lanToAdjoint . adjointToLan ≡ id
--

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 -- | lanToComposedAdjoint and composedAdjointToLan witness -- the natural isomorphism between Lan f h and Compose h -- g given f -| g -- --

--   composedAdjointToLan . lanToComposedAdjoint ≡ id
--   lanToComposedAdjoint . composedAdjointToLan ≡ id
--

lanToComposedAdjoint :: (Functor h, Adjunction f g) => Lan f h a -> h (g a) instance (Functor g, Applicative h) => Applicative (Lan g h) instance (Functor g, Apply h) => Apply (Lan g h) instance Functor (Lan f g) -- | The co-Yoneda lemma for a covariant Functor f states -- that Coyoneda f is naturally isomorphic to f. module Data.Functor.Coyoneda -- | A covariant Functor suitable for Yoneda reduction data Coyoneda f a Coyoneda :: (b -> a) -> f b -> Coyoneda f a -- | Yoneda "expansion" -- --

--   liftCoyoneda . lowerCoyoneda ≡ id
--   lowerCoyoneda . liftCoyoneda ≡ id
--

-- --

--   lowerCoyoneda (liftCoyoneda fa) = -- by definition
--   lowerCoyoneda (Coyoneda id fa)  = -- by definition
--   fmap id fa                      = -- functor law
--   fa
--

-- --

--   lift = liftCoyoneda
--

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

--   lower = lowerM = lowerCoyoneda
--

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

--   lower = lowerM = lowerCoyoneda
--

lowerM :: Monad f => Coyoneda f a -> f a -- | Coyoneda f is the left Kan extension of f along the -- Identity functor. -- --

--   coyonedaToLan . lanToCoyoneda ≡ id
--   lanToCoyoneda . coyonedaToLan ≡ id
--

coyonedaToLan :: Coyoneda f a -> Lan Identity f a lanToCoyoneda :: Lan Identity f a -> Coyoneda f a -- | Coyoneda f is the left Kan lift of f along -- the Identity functor. -- --

--   coyonedaToLift . liftToCoyoneda ≡ id
--   liftToCoyoneda . coyonedaToLift ≡ id
--

coyonedaToLift :: Coyoneda f a -> Lift Identity f a liftToCoyoneda :: Functor f => Lift Identity f a -> Coyoneda f a instance Adjunction f g => Adjunction (Coyoneda f) (Coyoneda g) instance (Functor f, Ord (f a)) => Ord (Coyoneda f a) instance (Functor f, Eq (f a)) => Eq (Coyoneda f a) instance (Functor f, Read (f a)) => Read (Coyoneda f a) instance (Functor f, Show (f a)) => Show (Coyoneda f a) instance Distributive f => Distributive (Coyoneda f) instance Traversable1 f => Traversable1 (Coyoneda f) instance Traversable f => Traversable (Coyoneda f) instance Foldable1 f => Foldable1 (Coyoneda f) instance Foldable f => Foldable (Coyoneda f) instance ComonadTrans Coyoneda instance Comonad w => Comonad (Coyoneda w) instance Extend w => Extend (Coyoneda w) instance Representable f => Representable (Coyoneda f) instance MonadPlus f => MonadPlus (Coyoneda f) instance MonadFix f => MonadFix (Coyoneda f) instance MonadTrans Coyoneda instance Monad m => Monad (Coyoneda m) instance Bind m => Bind (Coyoneda m) instance Plus f => Plus (Coyoneda f) instance Alt f => Alt (Coyoneda f) instance Alternative f => Alternative (Coyoneda f) instance Applicative f => Applicative (Coyoneda f) instance Apply f => Apply (Coyoneda f) instance Functor (Coyoneda f) -- | The Density Comonad for a Functor (aka the -- 'Comonad generated by a Functor) The Density term dates -- back to Dubuc''s 1974 thesis. The term Monad genererated by a -- Functor dates back to 1972 in Street''s ''Formal Theory of -- Monads''. -- -- The left Kan extension of a Functor along itself -- (Lan f f) forms a Comonad. This is that -- Comonad. module Control.Comonad.Density data Density k a Density :: (k b -> a) -> k b -> Density k a -- | The natural transformation from a Comonad w to the -- Comonad generated by w (forwards). -- -- This is merely a right-inverse (section) of lower, rather than -- a full inverse. -- --

--   lower . liftDensity ≡ id
--

liftDensity :: Comonad w => w a -> Density w a -- | The Density Comonad of a left adjoint is isomorphic to the -- Comonad formed by that Adjunction. -- -- This isomorphism is witnessed by densityToAdjunction and -- adjunctionToDensity. -- --

--   densityToAdjunction . adjunctionToDensity ≡ id
--   adjunctionToDensity . densityToAdjunction ≡ id
--

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 Density Comonad of a Functor f is -- obtained by taking the left Kan extension (Lan) of f -- along itself. This isomorphism is witnessed by lanToDensity and -- densityToLan -- --

--   lanToDensity . densityToLan ≡ id
--   densityToLan . lanToDensity ≡ id
--

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

--   Co w a ~ Rift w Identity a
--

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 (Comonad w, MonadError e m) => MonadError e (CoT w m) instance (Comonad w, MonadWriter e m) => MonadWriter e (CoT w m) instance (Comonad w, MonadState s m) => MonadState s (CoT w m) instance (Comonad w, MonadReader e m) => MonadReader e (CoT w m) instance (Comonad w, MonadIO m) => MonadIO (CoT w m) instance Comonad w => MonadTrans (CoT w) instance Comonad w => Monad (CoT w m) instance Comonad w => Applicative (CoT w m) instance Extend w => Bind (CoT w m) instance Extend w => Apply (CoT w m) instance Functor w => Functor (CoT w m)