kan-extensions-5.0.1: Kan extensions, Kan lifts, various forms of 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 `(>>=)`.

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

Constructors

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

Instances

 Source MonadReader r m => MonadState r (Codensity m) Source MonadReader r m => MonadReader r (Codensity m) Source (Functor f, MonadFree f m) => MonadFree f (Codensity m) Source Source Source Source Source Source MonadIO m => MonadIO (Codensity m) Source Plus v => Plus (Codensity v) Source Alt v => Alt (Codensity v) Source Source

lowerCodensity :: Applicative f => Codensity f a -> f 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`
```

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

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.