[Haskell-cafe] Monads that are Comonads and the role of Adjunction

[David Menendez]

On Dec 14, 2007 5:14 AM, Jules Bean <jules at jellybean.co.uk> wrote:

> There are two standard ways to decompose a monad into two adjoint
> functors: the Kleisli decomposition and the Eilenberg-Moore decomposition.
>
> However, neither of these categories is a subcategory of Hask in an
> obvious way, so I don't immediately see how to write "f" and "g" as
> haskell functors.
>
> Maybe someone else can show the way :)


One possibility is to extend Haskell's Functor class. We can define a class
of (some) categories whose objects are Haskell types:

> class Category mor where
>     id  :: mor a a
>     (.) :: mor b c -> mor a b -> mor a c

The instance for (->) should be obvious. We can also define an instance for
Kleisli operations:

> newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }
> instance (Monad m) => Category (Kleisli m) -- omitted

Next, a class for (some) functors between these categories:

> class (Category morS, Category morT) => Functor f morS morT where
>     fmap :: morS a b -> morT (f a) (f b)

Unlike the usual Haskell Functor class, this requires us to distinguish the
functor itself from the type constructor involved in the functor.

Here's an instance converting Kleisli operations to functions.

> instance Monad m => Functor m (Kleisli m) (->) where
>     -- fmap :: Kleisli m a b -> (m a -> m b)
>     fmap f = (>>= runKleisli f)

Going the other way is tricker, because our Functor interface requires a
type constructor. We'll use Id.

> newtype Id a = Id { unId :: a }
>
> instance Monad m => Functor Id (->) (Kleisli m) where
>     -- fmap :: (a -> b) -> Kleisli m (Id a) (Id b)
>     fmap f = Kleisli (return . Id . f . unId)

Finally, adjunctions between functors:

> class (Functor f morS morT, Functor g morT morS)
>     => Adjunction f g morS morT | f g morS -> morT, f g morT -> morS
>     where
>     leftAdj   :: morT (f a) b -> morS a (g b)
>     rightAdj  :: morS a (g b) -> morT (f a) b

The functional dependency isn't really justified. It's there to eliminate
ambiguity in the later code.

The two functors above are adjoint:

> instance (Monad m) => Adjunction Id m (->) (Kleisli m) where
>     -- leftAdj :: Kleisli (Id a) b -> (a -> m b)
>     leftAdj f = runKleisli f . Id
>
>     -- rightAdj :: (a -> m b) -> Kleisli (Id a) b
>     rightAdj f = Kleisli (f . unId)

So, given two adjoint functors, we have a monad and a comonad. Note,
however, that these aren't necessarily the same as the Haskell classes Monad
and Comonad.

Here are the monad operations:

> unit :: (Adjunction f g morS morT) => morS a (g(f a))
> unit = leftAdj id
>
> extend :: (Adjunction f g morS morT) => morS a (g(f b)) -> morS (g(f a))
(g(f b))
> extend f = fmap (rightAdj f)

The monad's type constructor is the composition of g and f. Extend
corresponds to (>>=) with the arguments reversed.

In our running example, unit and extend have these types:

    unit   :: Monad m => a -> m (Id a)
    extend :: Monad m => (a -> m (Id b)) -> m (Id a) -> m (Id b)

This corresponds to our original monad, only with the extra Id.

Here are the comonad operations:

> counit :: (Adjunction f g morS morT) => morT (f(g a)) a
> counit = rightAdj id
>
> coextend :: (Adjunction f g morS morT) => morT (f(g a)) b -> morT (f(g a))
(f(g b))
> coextend f = fmap (leftAdj f)

In our running example, counit and coextend have these types:

    counit   :: Monad m => Kleisli m (Id (m a)) a
    coextend :: Monad m => Kleisli m (Id (m a)) b -> Kleisli m (Id (m a))
(Id (m b))

Thus, m is effectively a comonad in its Kleisli category.

We can tell a similar story with Comonads and CoKleisli operations,
eventually reaching an adjunction like this:

> instance (Comonad w) => Adjunction w Id (CoKleisli w) (->) -- omitted

-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20071214/052226d6/attachment.htm