Copyright  (C) 20082013 Edward Kmett 

License  BSDstyle (see the file LICENSE) 
Maintainer  Edward Kmett <ekmett@gmail.com> 
Stability  provisional 
Portability  nonportable (rank2 polymorphism) 
Safe Haskell  Trustworthy 
Language  Haskell98 
 newtype Codensity m a = Codensity {
 runCodensity :: forall b. (a > m b) > m b
 lowerCodensity :: Monad m => Codensity m a > m a
 codensityToAdjunction :: Adjunction f g => Codensity g a > g (f a)
 adjunctionToCodensity :: Adjunction f g => g (f a) > Codensity g a
 codensityToRan :: Codensity g a > Ran g g a
 ranToCodensity :: Ran g g a > Codensity g a
 codensityToComposedRep :: Representable u => Codensity u a > u (Rep u, a)
 composedRepToCodensity :: Representable u => u (Rep u, a) > Codensity u a
 improve :: Functor f => (forall m. MonadFree f m => m a) > Free f a
Documentation
is the Monad generated by taking the right Kan extension
of any Codensity
fFunctor
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.
Codensity  

MonadTrans Codensity  
MonadReader r m => MonadState r (Codensity m)  
(Functor f, MonadFree f m) => MonadFree f (Codensity m)  
Alternative v => Alternative (Codensity v)  
Monad (Codensity f)  
Functor (Codensity k)  
MonadPlus v => MonadPlus (Codensity v)  
Applicative (Codensity f)  
MonadIO m => MonadIO (Codensity m)  
Plus v => Plus (Codensity v)  
Alt v => Alt (Codensity v)  
Apply (Codensity f) 
lowerCodensity :: Monad m => Codensity m a > m a Source
This serves as the *left*inverse (retraction) of lift
.
lowerCodensity
.lift
≡id
In general this is not a full 2sided inverse, merely a retraction, as
is often considerably "larger" than Codensity
mm
.
e.g.
could support a full complement of Codensity
((>) s)) a ~ forall r. (a > s > r) > s > r
actions, while MonadState
s(>) s
is limited to
actions.MonadReader
s
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
.adjunctionToCodensity
≡id
adjunctionToCodensity
.codensityToAdjunction
≡id
adjunctionToCodensity :: Adjunction f g => g (f a) > Codensity g 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
.ranToCodensity
≡id
ranToCodensity
.codensityToRan
≡id
ranToCodensity :: Ran g g a > Codensity g a Source
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
.composedRepToCodensity
≡id
composedRepToCodensity
.codensityToComposedRep
≡id
codensityToComposedRep =ranToComposedRep
.codensityToRan
composedRepToCodensity :: Representable u => u (Rep u, a) > Codensity u a Source
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.
See "Asymptotic Improvement of Computations over Free Monads" by Janis Voightländer for more information about this combinator.