I discovered them and bundled them up a year or so back in category-extras.
http://comonad.com/haskell/category-extras/dist/doc/html/category-extras/Control-Monad-Codensity.html I also wrote a series of blog posts including the derivation of these and their dual in the form of right- and left- Kan extensions. http://comonad.com/reader/2008/kan-extensions/ http://comonad.com/reader/2008/kan-extensions-ii/ http://comonad.com/reader/2008/kan-extension-iii/ I shared with Janis Voigtlaender the connection to his asymptotic improvement in the performance of free monads paper as well. After I discovered the connection between these and that paper shortly thereafter. -Edward Kmett On Wed, Apr 8, 2009 at 2:22 PM, Sebastian Fischer < s...@informatik.uni-kiel.de> wrote: > > {-# LANGUAGE Rank2Types #-} > > Dear Haskellers, > > I just realized that we get instances of `Monad` from pointed functors > and instances of `MonadPlus` from alternative functors. > > Is this folklore? > > > import Control.Monad > > import Control.Applicative > > In fact, every unary type constructor gives rise to a monad by the > continuation monad transformer. > > > newtype ContT t a = ContT { unContT :: forall r . (a -> t r) -> t r } > > > > instance Monad (ContT t) > > where > > return x = ContT ($x) > > m >>= f = ContT (\k -> unContT m (\x -> unContT (f x) k)) > > Both the `mtl` package and the `transformers` package use the same > `Monad` instance for their `ContT` type but require `t` to be an > instance of `Monad`. Why? [^1] > > If `f` is an applicative functor (in fact, a pointed functor is > enough), then we can translate monadic actions back to the original > type. > > > runContT :: Applicative f => ContT f a -> f a > > runContT m = unContT m pure > > If `f` is an alternative functor, then `ContT f` is a `MonadPlus`. > > > instance Alternative f => MonadPlus (ContT f) > > where > > mzero = ContT (const empty) > > a `mplus` b = ContT (\k -> unContT a k <|> unContT b k) > > That is no surprise because `empty` and `<|>` are just renamings for > `mzero` and `mplus` (or the other way round). The missing piece was > `>>=` which is provided by `ContT` for free. > > Are these instances defined somewhere? > > Cheers, > Sebastian > > [^1] I recognized that Janis Voigtlaender defines the type `ContT` > under the name `C` in Section 3 of his paper on "Asymptotic > Improvement of Computations over Free Monads" (available at > http://wwwtcs.inf.tu-dresden.de/~voigt/mpc08.pdf) and gives a monad > instance without constraints on the first parameter. > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe