kan-extensions-3.5: Kan extensions, Kan lifts, various forms of the Yoneda lemma, and (co)density (co)monads

Portabilitynon-portable (rank-2 polymorphism)
Stabilityprovisional
MaintainerEdward Kmett <ekmett@gmail.com>
Safe HaskellTrustworthy

Control.Monad.Codensity

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

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

Constructors

Codensity 

Fields

runCodensity :: forall b. (a -> m b) -> m b
 

lowerCodensity :: Monad m => Codensity m a -> m aSource

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.

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

The Codensity monad of a right adjoint is isomorphic to the monad obtained from the Adjunction.

 codensityToAdjunction . adjunctionToCodensityid
 adjunctionToCodensity . codensityToAdjunctionid

codensityToRan :: Codensity g a -> Ran g g aSource

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 (Key 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 aSource

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