kan-extensions-5.2: Kan extensions, Kan lifts, the Yoneda lemma, and (co)density (co)monads

Copyright(C) 2011-2016 Edward Kmett
LicenseBSD-style (see the file LICENSE)
MaintainerEdward Kmett <ekmett@gmail.com>
Stabilityprovisional
PortabilityGADTs, MPTCs, fundeps
Safe HaskellTrustworthy
LanguageHaskell98

Data.Functor.Coyoneda

Contents

Description

The co-Yoneda lemma for a covariant Functor f states that Coyoneda f is naturally isomorphic to f.

Synopsis

Documentation

data Coyoneda f a where Source #

A covariant Functor suitable for Yoneda reduction

Constructors

Coyoneda :: (b -> a) -> f b -> Coyoneda f a 
Instances
ComonadTrans Coyoneda Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

lower :: Comonad w => Coyoneda w a -> w a #

MonadTrans Coyoneda Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

lift :: Monad m => m a -> Coyoneda m a #

Monad m => Monad (Coyoneda m) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

(>>=) :: Coyoneda m a -> (a -> Coyoneda m b) -> Coyoneda m b #

(>>) :: Coyoneda m a -> Coyoneda m b -> Coyoneda m b #

return :: a -> Coyoneda m a #

fail :: String -> Coyoneda m a #

Functor (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

fmap :: (a -> b) -> Coyoneda f a -> Coyoneda f b #

(<$) :: a -> Coyoneda f b -> Coyoneda f a #

MonadFix f => MonadFix (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

mfix :: (a -> Coyoneda f a) -> Coyoneda f a #

Applicative f => Applicative (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

pure :: a -> Coyoneda f a #

(<*>) :: Coyoneda f (a -> b) -> Coyoneda f a -> Coyoneda f b #

liftA2 :: (a -> b -> c) -> Coyoneda f a -> Coyoneda f b -> Coyoneda f c #

(*>) :: Coyoneda f a -> Coyoneda f b -> Coyoneda f b #

(<*) :: Coyoneda f a -> Coyoneda f b -> Coyoneda f a #

Foldable f => Foldable (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

fold :: Monoid m => Coyoneda f m -> m #

foldMap :: Monoid m => (a -> m) -> Coyoneda f a -> m #

foldr :: (a -> b -> b) -> b -> Coyoneda f a -> b #

foldr' :: (a -> b -> b) -> b -> Coyoneda f a -> b #

foldl :: (b -> a -> b) -> b -> Coyoneda f a -> b #

foldl' :: (b -> a -> b) -> b -> Coyoneda f a -> b #

foldr1 :: (a -> a -> a) -> Coyoneda f a -> a #

foldl1 :: (a -> a -> a) -> Coyoneda f a -> a #

toList :: Coyoneda f a -> [a] #

null :: Coyoneda f a -> Bool #

length :: Coyoneda f a -> Int #

elem :: Eq a => a -> Coyoneda f a -> Bool #

maximum :: Ord a => Coyoneda f a -> a #

minimum :: Ord a => Coyoneda f a -> a #

sum :: Num a => Coyoneda f a -> a #

product :: Num a => Coyoneda f a -> a #

Traversable f => Traversable (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

traverse :: Applicative f0 => (a -> f0 b) -> Coyoneda f a -> f0 (Coyoneda f b) #

sequenceA :: Applicative f0 => Coyoneda f (f0 a) -> f0 (Coyoneda f a) #

mapM :: Monad m => (a -> m b) -> Coyoneda f a -> m (Coyoneda f b) #

sequence :: Monad m => Coyoneda f (m a) -> m (Coyoneda f a) #

Distributive f => Distributive (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

distribute :: Functor f0 => f0 (Coyoneda f a) -> Coyoneda f (f0 a) #

collect :: Functor f0 => (a -> Coyoneda f b) -> f0 a -> Coyoneda f (f0 b) #

distributeM :: Monad m => m (Coyoneda f a) -> Coyoneda f (m a) #

collectM :: Monad m => (a -> Coyoneda f b) -> m a -> Coyoneda f (m b) #

Representable f => Representable (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Associated Types

type Rep (Coyoneda f) :: Type #

Methods

tabulate :: (Rep (Coyoneda f) -> a) -> Coyoneda f a #

index :: Coyoneda f a -> Rep (Coyoneda f) -> a #

Eq1 f => Eq1 (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

liftEq :: (a -> b -> Bool) -> Coyoneda f a -> Coyoneda f b -> Bool #

Ord1 f => Ord1 (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

liftCompare :: (a -> b -> Ordering) -> Coyoneda f a -> Coyoneda f b -> Ordering #

Read1 f => Read1 (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Coyoneda f a) #

liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [Coyoneda f a] #

liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (Coyoneda f a) #

liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [Coyoneda f a] #

(Functor f, Show1 f) => Show1 (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Coyoneda f a -> ShowS #

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Coyoneda f a] -> ShowS #

Alternative f => Alternative (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

empty :: Coyoneda f a #

(<|>) :: Coyoneda f a -> Coyoneda f a -> Coyoneda f a #

some :: Coyoneda f a -> Coyoneda f [a] #

many :: Coyoneda f a -> Coyoneda f [a] #

MonadPlus f => MonadPlus (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

mzero :: Coyoneda f a #

mplus :: Coyoneda f a -> Coyoneda f a -> Coyoneda f a #

Comonad w => Comonad (Coyoneda w) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

extract :: Coyoneda w a -> a #

duplicate :: Coyoneda w a -> Coyoneda w (Coyoneda w a) #

extend :: (Coyoneda w a -> b) -> Coyoneda w a -> Coyoneda w b #

Traversable1 f => Traversable1 (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

traverse1 :: Apply f0 => (a -> f0 b) -> Coyoneda f a -> f0 (Coyoneda f b) #

sequence1 :: Apply f0 => Coyoneda f (f0 b) -> f0 (Coyoneda f b) #

Foldable1 f => Foldable1 (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

fold1 :: Semigroup m => Coyoneda f m -> m #

foldMap1 :: Semigroup m => (a -> m) -> Coyoneda f a -> m #

toNonEmpty :: Coyoneda f a -> NonEmpty a #

Plus f => Plus (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

zero :: Coyoneda f a #

Alt f => Alt (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

(<!>) :: Coyoneda f a -> Coyoneda f a -> Coyoneda f a #

some :: Applicative (Coyoneda f) => Coyoneda f a -> Coyoneda f [a] #

many :: Applicative (Coyoneda f) => Coyoneda f a -> Coyoneda f [a] #

Apply f => Apply (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

(<.>) :: Coyoneda f (a -> b) -> Coyoneda f a -> Coyoneda f b #

(.>) :: Coyoneda f a -> Coyoneda f b -> Coyoneda f b #

(<.) :: Coyoneda f a -> Coyoneda f b -> Coyoneda f a #

liftF2 :: (a -> b -> c) -> Coyoneda f a -> Coyoneda f b -> Coyoneda f c #

Bind m => Bind (Coyoneda m) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

(>>-) :: Coyoneda m a -> (a -> Coyoneda m b) -> Coyoneda m b #

join :: Coyoneda m (Coyoneda m a) -> Coyoneda m a #

Extend w => Extend (Coyoneda w) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

duplicated :: Coyoneda w a -> Coyoneda w (Coyoneda w a) #

extended :: (Coyoneda w a -> b) -> Coyoneda w a -> Coyoneda w b #

Adjunction f g => Adjunction (Coyoneda f) (Coyoneda g) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

unit :: a -> Coyoneda g (Coyoneda f a) #

counit :: Coyoneda f (Coyoneda g a) -> a #

leftAdjunct :: (Coyoneda f a -> b) -> a -> Coyoneda g b #

rightAdjunct :: (a -> Coyoneda g b) -> Coyoneda f a -> b #

(Functor f, Eq1 f, Eq a) => Eq (Coyoneda f a) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

(==) :: Coyoneda f a -> Coyoneda f a -> Bool #

(/=) :: Coyoneda f a -> Coyoneda f a -> Bool #

(Functor f, Ord1 f, Ord a) => Ord (Coyoneda f a) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

compare :: Coyoneda f a -> Coyoneda f a -> Ordering #

(<) :: Coyoneda f a -> Coyoneda f a -> Bool #

(<=) :: Coyoneda f a -> Coyoneda f a -> Bool #

(>) :: Coyoneda f a -> Coyoneda f a -> Bool #

(>=) :: Coyoneda f a -> Coyoneda f a -> Bool #

max :: Coyoneda f a -> Coyoneda f a -> Coyoneda f a #

min :: Coyoneda f a -> Coyoneda f a -> Coyoneda f a #

Read (f a) => Read (Coyoneda f a) Source # 
Instance details

Defined in Data.Functor.Coyoneda

(Functor f, Show1 f, Show a) => Show (Coyoneda f a) Source # 
Instance details

Defined in Data.Functor.Coyoneda

Methods

showsPrec :: Int -> Coyoneda f a -> ShowS #

show :: Coyoneda f a -> String #

showList :: [Coyoneda f a] -> ShowS #

type Rep (Coyoneda f) Source # 
Instance details

Defined in Data.Functor.Coyoneda

type Rep (Coyoneda f) = Rep f

liftCoyoneda :: f a -> Coyoneda f a Source #

Yoneda "expansion"

liftCoyoneda . lowerCoyonedaid
lowerCoyoneda . liftCoyonedaid
lowerCoyoneda (liftCoyoneda fa) = -- by definition
lowerCoyoneda (Coyoneda id fa)  = -- by definition
fmap id fa                      = -- functor law
fa
lift = liftCoyoneda

lowerCoyoneda :: Functor f => Coyoneda f a -> f a Source #

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

lowerM :: Monad f => Coyoneda f a -> f a Source #

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

hoistCoyoneda :: (forall a. f a -> g a) -> Coyoneda f b -> Coyoneda g b Source #

Lift a natural transformation from f to g to a natural transformation from Coyoneda f to Coyoneda g.

as a Left Kan extension

coyonedaToLan :: Coyoneda f a -> Lan Identity f a Source #

Coyoneda f is the left Kan extension of f along the Identity functor.

Coyoneda f is always a functor, even if f is not. In this case, it is called the free functor over f. 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 Identity functor, but along the inclusion functor from the discrete subcategory of Hask 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.)

coyonedaToLan . lanToCoyonedaid
lanToCoyoneda . coyonedaToLanid