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

Copyright (C) 2008-2016 Edward Kmett BSD-style (see the file LICENSE) Edward Kmett provisional non-portable (rank-2 polymorphism) Trustworthy Haskell98

Description

Synopsis

# Documentation

newtype Codensity m a Source #

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 (>>=).

Constructors

 Codensity FieldsrunCodensity :: forall b. (a -> m b) -> m b

Instances

 MonadReader r m => MonadReader r (Codensity * m) Source # Methodsask :: Codensity * m r #local :: (r -> r) -> Codensity * m a -> Codensity * m a #reader :: (r -> a) -> Codensity * m a # MonadReader r m => MonadState r (Codensity * m) Source # Methodsget :: Codensity * m r #put :: r -> Codensity * m () #state :: (r -> (a, r)) -> Codensity * m a # (Functor f, MonadFree f m) => MonadFree f (Codensity * m) Source # Methodswrap :: f (Codensity * m a) -> Codensity * m a # Source # Methodslift :: Monad m => m a -> Codensity * m a # Monad (Codensity k f) Source # Methods(>>=) :: Codensity k f a -> (a -> Codensity k f b) -> Codensity k f b #(>>) :: Codensity k f a -> Codensity k f b -> Codensity k f b #return :: a -> Codensity k f a #fail :: String -> Codensity k f a # Functor (Codensity k1 k2) Source # Methodsfmap :: (a -> b) -> Codensity k1 k2 a -> Codensity k1 k2 b #(<\$) :: a -> Codensity k1 k2 b -> Codensity k1 k2 a # MonadFail f => MonadFail (Codensity * f) Source # Methodsfail :: String -> Codensity * f a # Applicative (Codensity k f) Source # Methodspure :: a -> Codensity k f a #(<*>) :: Codensity k f (a -> b) -> Codensity k f a -> Codensity k f b #liftA2 :: (a -> b -> c) -> Codensity k f a -> Codensity k f b -> Codensity k f c #(*>) :: Codensity k f a -> Codensity k f b -> Codensity k f b #(<*) :: Codensity k f a -> Codensity k f b -> Codensity k f a # MonadIO m => MonadIO (Codensity * m) Source # MethodsliftIO :: IO a -> Codensity * m a # Source # Methodsempty :: Codensity * v a #(<|>) :: Codensity * v a -> Codensity * v a -> Codensity * v a #some :: Codensity * v a -> Codensity * v [a] #many :: Codensity * v a -> Codensity * v [a] # Source # Methodsmzero :: Codensity * v a #mplus :: Codensity * v a -> Codensity * v a -> Codensity * v a # Plus v => Plus (Codensity * v) Source # Methodszero :: Codensity * v a # Alt v => Alt (Codensity * v) Source # Methods() :: Codensity * v a -> Codensity * v a -> Codensity * v a #some :: Applicative (Codensity * v) => Codensity * v a -> Codensity * v [a] #many :: Applicative (Codensity * v) => Codensity * v a -> Codensity * v [a] # Apply (Codensity k f) Source # Methods(<.>) :: Codensity k f (a -> b) -> Codensity k f a -> Codensity k f b #(.>) :: Codensity k f a -> Codensity k f b -> Codensity k f b #(<.) :: Codensity k f a -> Codensity k f b -> Codensity k f a #liftF2 :: (a -> b -> c) -> Codensity k f a -> Codensity k f b -> Codensity k f c #

lowerCodensity :: Applicative f => Codensity f a -> f a Source #

This serves as the *left*-inverse (retraction) of lift.

lowerCodensity . liftid

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.

codensityToAdjunction :: Adjunction f g => Codensity g a -> g (f a) Source #

codensityToRan :: Codensity g a -> Ran g g a Source #

The Codensity Monad of a Functor g is the right Kan extension (Ran) of g along itself.

codensityToRan . ranToCodensityid
ranToCodensity . codensityToRanid

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

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 . composedRepToCodensityid
composedRepToCodensity . codensityToComposedRepid
codensityToComposedRep = ranToComposedRep . codensityToRan

improve :: Functor f => (forall m. MonadFree f m => m a) -> Free f a Source #

Right associate all binds in a computation that generates a free monad

This can improve the asymptotic efficiency of the result, while preserving semantics.