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

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

Data.Functor.Coyoneda

Contents

- as a Left Kan extension

Description

``Coyoneda` f` is the "free functor" over `f`. The co-Yoneda lemma for a covariant `Functor` `f` states that ``Coyoneda` f` is naturally isomorphic to `f`.

Synopsis

- data Coyoneda (f :: Type -> Type) a where
  - Coyoneda :: forall b a (f :: Type -> Type). (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 :: forall (f :: Type -> Type) a. Coyoneda f a -> Lan Identity f a
- lanToCoyoneda :: forall (f :: Type -> Type) a. Lan Identity f a -> Coyoneda f a

# Documentation

data Coyoneda (f :: Type -> Type) a where Source #

A covariant `Functor` suitable for Yoneda reduction

Constructors

Coyoneda :: forall b a (f :: Type -> Type). (b -> a) -> f b -> Coyoneda f a |

#### Instances

Instances details

ComonadTrans Coyoneda Source # |
Instance details Defined in Data.Functor.Coyoneda Methods lower :: Comonad w => Coyoneda w a -> w a Source #
MonadTrans Coyoneda Source # |
Instance details Defined in Data.Functor.Coyoneda Methods lift :: Monad m => m a -> Coyoneda m a Source #
Representable f => Representable (Coyoneda f) Source # |

Instance details

Defined in Data.Functor.Coyoneda

Associated Types

type Rep (Coyoneda f) |
Instance details Defined in Data.Functor.Coyoneda type Rep (Coyoneda f) = Rep f

Methods

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

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

Foldable1 f => Foldable1 (Coyoneda f) Source # |

Instance details

Defined in Data.Functor.Coyoneda

Methods

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

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

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

toNonEmpty :: Coyoneda f a -> NonEmpty a Source #

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

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

head :: Coyoneda f a -> a Source #

last :: Coyoneda f a -> a Source #

foldrMap1 :: (a -> b) -> (a -> b -> b) -> Coyoneda f a -> b Source #

foldlMap1' :: (a -> b) -> (b -> a -> b) -> Coyoneda f a -> b Source #

foldlMap1 :: (a -> b) -> (b -> a -> b) -> Coyoneda f a -> b Source #

foldrMap1' :: (a -> b) -> (a -> b -> b) -> Coyoneda f a -> b Source #

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 Source #
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 Source #
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) Source # liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [Coyoneda f a] Source # liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (Coyoneda f a) Source # liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [Coyoneda f a] Source #
(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 Source # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Coyoneda f a] -> ShowS Source #
Comonad w => Comonad (Coyoneda w) Source # |
Instance details Defined in Data.Functor.Coyoneda Methods extract :: Coyoneda w a -> a Source # duplicate :: Coyoneda w a -> Coyoneda w (Coyoneda w a) Source # extend :: (Coyoneda w a -> b) -> Coyoneda w a -> Coyoneda w b Source #
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) Source # collect :: Functor f0 => (a -> Coyoneda f b) -> f0 a -> Coyoneda f (f0 b) Source # distributeM :: Monad m => m (Coyoneda f a) -> Coyoneda f (m a) Source # collectM :: Monad m => (a -> Coyoneda f b) -> m a -> Coyoneda f (m b) Source #
Alternative f => Alternative (Coyoneda f) Source # |
Instance details Defined in Data.Functor.Coyoneda Methods empty :: Coyoneda f a Source # (<|>) :: Coyoneda f a -> Coyoneda f a -> Coyoneda f a Source # some :: Coyoneda f a -> Coyoneda f [a] Source # many :: Coyoneda f a -> Coyoneda f [a] Source #
Applicative f => Applicative (Coyoneda f) Source # |
Instance details Defined in Data.Functor.Coyoneda Methods pure :: a -> Coyoneda f a Source # (<*>) :: Coyoneda f (a -> b) -> Coyoneda f a -> Coyoneda f b Source # liftA2 :: (a -> b -> c) -> Coyoneda f a -> Coyoneda f b -> Coyoneda f c Source # (*>) :: Coyoneda f a -> Coyoneda f b -> Coyoneda f b Source # (<*) :: Coyoneda f a -> Coyoneda f b -> Coyoneda f a Source #
Functor (Coyoneda f) Source # |
Instance details Defined in Data.Functor.Coyoneda Methods fmap :: (a -> b) -> Coyoneda f a -> Coyoneda f b Source # (<$) :: a -> Coyoneda f b -> Coyoneda f a Source #
Monad m => Monad (Coyoneda m) Source # |
Instance details Defined in Data.Functor.Coyoneda Methods (>>=) :: Coyoneda m a -> (a -> Coyoneda m b) -> Coyoneda m b Source # (>>) :: Coyoneda m a -> Coyoneda m b -> Coyoneda m b Source # return :: a -> Coyoneda m a Source #
MonadPlus f => MonadPlus (Coyoneda f) Source # |
Instance details Defined in Data.Functor.Coyoneda Methods mzero :: Coyoneda f a Source # mplus :: Coyoneda f a -> Coyoneda f a -> Coyoneda f a Source #
MonadFix f => MonadFix (Coyoneda f) Source # |
Instance details Defined in Data.Functor.Coyoneda Methods mfix :: (a -> Coyoneda f a) -> Coyoneda f a Source #
Foldable f => Foldable (Coyoneda f) Source # |

Instance details

Defined in Data.Functor.Coyoneda

Methods

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

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

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

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

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

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

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

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

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

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

null :: Coyoneda f a -> Bool Source #

length :: Coyoneda f a -> Int Source #

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

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

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

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

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

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) Source # sequenceA :: Applicative f0 => Coyoneda f (f0 a) -> f0 (Coyoneda f a) Source # mapM :: Monad m => (a -> m b) -> Coyoneda f a -> m (Coyoneda f b) Source # sequence :: Monad m => Coyoneda f (m a) -> m (Coyoneda f a) Source #
Alt f => Alt (Coyoneda f) Source # |
Instance details Defined in Data.Functor.Coyoneda Methods (<!>) :: Coyoneda f a -> Coyoneda f a -> Coyoneda f a Source # some :: Applicative (Coyoneda f) => Coyoneda f a -> Coyoneda f [a] Source # many :: Applicative (Coyoneda f) => Coyoneda f a -> Coyoneda f [a] Source #
Apply f => Apply (Coyoneda f) Source # |
Instance details Defined in Data.Functor.Coyoneda Methods (<.>) :: Coyoneda f (a -> b) -> Coyoneda f a -> Coyoneda f b Source # (.>) :: Coyoneda f a -> Coyoneda f b -> Coyoneda f b Source # (<.) :: Coyoneda f a -> Coyoneda f b -> Coyoneda f a Source # liftF2 :: (a -> b -> c) -> Coyoneda f a -> Coyoneda f b -> Coyoneda f c Source #
Bind m => Bind (Coyoneda m) Source # |
Instance details Defined in Data.Functor.Coyoneda Methods (>>-) :: Coyoneda m a -> (a -> Coyoneda m b) -> Coyoneda m b Source # join :: Coyoneda m (Coyoneda m a) -> Coyoneda m a Source #
Extend w => Extend (Coyoneda w) Source # |
Instance details Defined in Data.Functor.Coyoneda Methods duplicated :: Coyoneda w a -> Coyoneda w (Coyoneda w a) Source # extended :: (Coyoneda w a -> b) -> Coyoneda w a -> Coyoneda w b Source #
Plus f => Plus (Coyoneda f) Source # |
Instance details Defined in Data.Functor.Coyoneda Methods zero :: Coyoneda f a Source #
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) Source # sequence1 :: Apply f0 => Coyoneda f (f0 b) -> f0 (Coyoneda f b) Source #
Adjunction f g => Adjunction (Coyoneda f) (Coyoneda g) Source # |
Instance details Defined in Data.Functor.Coyoneda Methods unit :: a -> Coyoneda g (Coyoneda f a) Source # counit :: Coyoneda f (Coyoneda g a) -> a Source # leftAdjunct :: (Coyoneda f a -> b) -> a -> Coyoneda g b Source # rightAdjunct :: (a -> Coyoneda g b) -> Coyoneda f a -> b Source #
Read (f a) => Read (Coyoneda f a) Source # |
Instance details Defined in Data.Functor.Coyoneda Methods readsPrec :: Int -> ReadS (Coyoneda f a) Source # readList :: ReadS [Coyoneda f a] Source # readPrec :: ReadPrec (Coyoneda f a) Source # readListPrec :: ReadPrec [Coyoneda f a] Source #
(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 Source # show :: Coyoneda f a -> String Source # showList :: [Coyoneda f a] -> ShowS Source #
(Eq1 f, Eq a) => Eq (Coyoneda f a) Source # |
Instance details Defined in Data.Functor.Coyoneda Methods (==) :: Coyoneda f a -> Coyoneda f a -> Bool Source # (/=) :: Coyoneda f a -> Coyoneda f a -> Bool Source #
(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 Source #

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

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

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

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

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

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

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 :: forall (f :: Type -> Type) a. 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 :: forall (f :: Type -> Type) a. Lan Identity f a -> Coyoneda f a Source #