Tue 28 Jun 2011

## Monad Transformers from Comonads

Posted by Edward Kmett under Category Theory , Comonads , Data Structures , Haskell , Kan Extensions , Monads1 Comment

Last time, I showed that we can transform any Comonad in Haskell into a Monad in Haskell.

Today, I'll show that we can go one step further and derive a monad transformer from any comonad!

**A Comonad to Monad-Transformer Transformer**

Given

newtype CoT w m a = CoT { runCoT :: forall r. w (a -> m r) -> m r }

we can easily embed the type of the previous `Co`

and create a smart constructor and deconstructor in the style of the MTL.

type Co w = CoT w Identity co :: Functor w => (forall r. w (a -> r) -> r) -> Co w a co f = CoT (Identity . f . fmap (fmap runIdentity)) runCo :: Functor w => Co w a -> w (a -> r) -> r runCo m = runIdentity . runCoT m . fmap (fmap Identity)

In fact, as with between Cont and ContT, none of the major instances even change!

instance Functor w => Functor (CoT w m) where fmap f (CoT w) = CoT (w . fmap (. f)) instance Extend w => Apply (CoT w m) where mf < .> ma = mf >>- \f -> fmap f ma instance Extend w => Bind (CoT w m) where CoT k >>- f = CoT (k . extend (\wa a -> runCoT (f a) wa)) instance Comonad w => Applicative (CoT w m) where pure a = CoT (`extract` a) mf < *> ma = mf >>= \f -> fmap f ma instance Comonad w => Monad (CoT w m) where return a = CoT (`extract` a) CoT k >>= f = CoT (k . extend (\wa a -> runCoT (f a) wa))

We can use CoT as a Monad transformer, or lift IO actions:

instance Comonad w => MonadTrans (CoT w) where lift m = CoT (extract . fmap (m >>=)) instance (Comonad w, MonadIO m) => MonadIO (CoT w m) where liftIO = lift . liftIO

(This monad transformer is available in my kan-extensions package as of 1.9.0 on hackage.)

And as before we can lift and lower CoKleisli arrows, although the results are monadic when lowered.

liftCoT0 :: Comonad w => (forall a. w a -> s) -> CoT w m s liftCoT0 f = CoT (extract < *> f) lowerCoT0 :: (Functor w, Monad m) => CoT w m s -> w a -> m s lowerCoT0 m = runCoT m . (return < $) lowerCo0 :: Functor w => Co w s -> w a -> s lowerCo0 m = runIdentity . runCoT m . (return < $) liftCoT1 :: (forall a. w a -> a) -> CoT w m () liftCoT1 f = CoT (`f` ()) lowerCoT1 :: (Functor w, Monad m) => CoT w m () -> w a -> m a lowerCoT1 m = runCoT m . fmap (const . return) lowerCo1 :: Functor w => Co w () -> w a -> a lowerCo1 m = runIdentity . runCoT m . fmap (const . return)

Since we could mean the MonadFoo instance derived from its comonadic equivalent or from the one we wrap as a monad transformer, we choose to default to the one from the monad, but we can still provide the lifted comonadic actions:

posW :: (ComonadStore s w, Monad m) => CoT w m s posW = liftCoT0 pos peekW :: (ComonadStore s w, Monad m) => s -> CoT w m () peekW s = liftCoT1 (peek s) peeksW :: (ComonadStore s w, Monad m) => (s -> s) -> CoT w m () peeksW f = liftCoT1 (peeks f) askW :: (ComonadEnv e w, Monad m) => CoT w m e askW = liftCoT0 (Env.ask) asksW :: (ComonadEnv e w, Monad m) => (e -> a) -> CoT w m a asksW f = liftCoT0 (Env.asks f) traceW :: (ComonadTraced e w, Monad m) => e -> CoT w m () traceW e = liftCoT1 (Traced.trace e)

and we just lift the monadic actions as usual:

instance (Comonad w, MonadReader e m) => MonadReader e (CoT w m) where ask = lift Reader.ask local f m = CoT (local f . runCoT m) instance (Comonad w, MonadState s m) => MonadState s (CoT w m) where get = lift get put = lift . put instance (Comonad w, MonadWriter e m) => MonadWriter e (CoT w m) where tell = lift . tell pass m = CoT (pass . runCoT m . fmap aug) where aug f (a,e) = liftM (\r -> (r,e)) (f a) listen = error "Control.Monad.Co.listen: TODO" instance (Comonad w, MonadError e m) => MonadError e (CoT w m) where throwError = lift . throwError catchError = error "Control.Monad.Co.catchError: TODO" instance (Comonad w, MonadCont m) => MonadCont (CoT w m) where callCC = error "Control.Monad.Co.callCC: TODO"

I welcome help working through the missing methods above.

This should go a long way towards showing the fact that there are strictly fewer comonads than monads in Haskell, and of course that there are no analogues to IO, STM and ST s in the world of Haskell comonads!

Every comonad gives you a monad-transformer, but not every monad is a monad transformer.

June 30th, 2011 at 2:18 pm

[...] time in Monad Transformers from Comonads I showed that given any comonad we can derive the [...]