Copyright	(C) 2008-2013 Edward Kmett
License	BSD-style (see the file LICENSE)
Maintainer	Edward Kmett <ekmett@gmail.com>
Stability	provisional
Portability	non-portable (rank-2 polymorphism)
Safe Haskell	Trustworthy
Language	Haskell98

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

Instances

MonadTrans Codensity Source
Methods lift :: Monad m => m a -> Codensity m a
MonadReader r m => MonadState r (Codensity m) Source
Methods get :: Codensity m r put :: r -> Codensity m () state :: (r -> (a, r)) -> Codensity m a
MonadReader r m => MonadReader r (Codensity m) Source
Methods ask :: Codensity m r local :: (r -> r) -> Codensity m a -> Codensity m a reader :: (r -> a) -> Codensity m a
(Functor f, MonadFree f m) => MonadFree f (Codensity m) Source
Methods wrap :: f (Codensity m a) -> Codensity m a
Monad (Codensity f) Source
Methods (>>=) :: Codensity f a -> (a -> Codensity f b) -> Codensity f b (>>) :: Codensity f a -> Codensity f b -> Codensity f b return :: a -> Codensity f a fail :: String -> Codensity f a
Functor (Codensity k) Source
Methods fmap :: (a -> b) -> Codensity k a -> Codensity k b (<$) :: a -> Codensity k b -> Codensity k a
Applicative (Codensity f) Source
Methods pure :: a -> Codensity f a (<>) :: Codensity f (a -> b) -> Codensity f a -> Codensity f b (>) :: Codensity f a -> Codensity f b -> Codensity f b (<*) :: Codensity f a -> Codensity f b -> Codensity f a
Alternative v => Alternative (Codensity v) Source
Methods empty :: 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]
MonadPlus v => MonadPlus (Codensity v) Source
Methods mzero :: Codensity v a mplus :: Codensity v a -> Codensity v a -> Codensity v a
MonadIO m => MonadIO (Codensity m) Source
Methods liftIO :: IO a -> Codensity m a
Plus v => Plus (Codensity v) Source
Methods zero :: 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 f) Source
Methods (<.>) :: Codensity f (a -> b) -> Codensity f a -> Codensity f b (.>) :: Codensity f a -> Codensity f b -> Codensity f b (<.) :: Codensity f a -> Codensity f b -> Codensity f a

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

composedRepToCodensity = ranToCodensity . composedRepToRan

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.

http://www.iai.uni-bonn.de/~jv/mpc08.pdf