Control.Monad.Codensity

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 Voigtländer for more information about this type.

https://www.janis-voigtlaender.eu/papers/AsymptoticImprovementOfComputationsOverFreeMonads.pdf

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.

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

codensityToAdjunction . adjunctionToCodensity ≡ id
adjunctionToCodensity . codensityToAdjunction ≡ id

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

codensityToRan . ranToCodensity ≡ id
ranToCodensity . codensityToRan ≡ id

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

Wrap the remainder of the Codensity action using the given function.

This function can be used to register cleanup actions that will be executed at the end. Example:

wrapCodensity (`finally` putStrLn "Done.")

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

reset m delimits the continuation of any shift inside m.

• reset (return m) = return m

shift f captures the continuation up to the nearest enclosing reset and passes it to f:

• reset (shift f >>= k) = reset (f (lowerCodensity . k))