Copyright	(C) 2011-2016 Edward Kmett
License	BSD-style (see the file LICENSE)
Maintainer	Edward Kmett <ekmett@gmail.com>
Stability	provisional
Portability	GADTs, MPTCs, fundeps
Safe Haskell	Trustworthy
Language	Haskell98

Data.Functor.Coyoneda

Contents

as a Left Kan extension

Description

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

Synopsis

data Coyoneda f a where
- Coyoneda :: (b -> a) -> f b -> Coyoneda f a
liftCoyoneda :: f a -> Coyoneda f a
lowerCoyoneda :: Functor f => Coyoneda f a -> f a
lowerM :: Monad f => Coyoneda f a -> f a
hoistCoyoneda :: (forall a. f a -> g a) -> Coyoneda f b -> Coyoneda g b
coyonedaToLan :: Coyoneda f a -> Lan Identity f a
lanToCoyoneda :: Lan Identity f a -> Coyoneda f a

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 Methods readsPrec :: Int -> ReadS (Coyoneda f a) # readList :: ReadS [Coyoneda f a] # readPrec :: ReadPrec (Coyoneda f a) # readListPrec :: ReadPrec [Coyoneda f a] #
(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 . lowerCoyoneda ≡ id
lowerCoyoneda . liftCoyoneda ≡ id

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 . lanToCoyoneda ≡ id
lanToCoyoneda . coyonedaToLan ≡ id

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