<br><br><div class="gmail_quote">On Dec 14, 2007 5:14 AM, Jules Bean <<a href="mailto:jules@jellybean.co.uk">jules@jellybean.co.uk</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
There are two standard ways to decompose a monad into two adjoint<br>functors: the Kleisli decomposition and the Eilenberg-Moore decomposition.<br><br>However, neither of these categories is a subcategory of Hask in an<br>
obvious way, so I don't immediately see how to write "f" and "g" as<br>haskell functors.<br><br>Maybe someone else can show the way :)<font color="#888888"></font></blockquote><div><br>One possibility is to extend Haskell's Functor class. We can define a class of (some) categories whose objects are Haskell types:
<br><br>> class Category mor where<br>> id :: mor a a<br>> (.) :: mor b c -> mor a b -> mor a c<br><br>The instance for (->) should be obvious. We can also define an instance for Kleisli operations:
<br><br>> newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }<br>> instance (Monad m) => Category (Kleisli m) -- omitted<br><br>Next, a class for (some) functors between these categories:<br><br>> class (Category morS, Category morT) => Functor f morS morT where
<br>> fmap :: morS a b -> morT (f a) (f b)<br><br>Unlike the usual Haskell Functor class, this requires us to distinguish the functor itself from the type constructor involved in the functor.<br><br>Here's an instance converting Kleisli operations to functions.
<br><br>> instance Monad m => Functor m (Kleisli m) (->) where<br>> -- fmap :: Kleisli m a b -> (m a -> m b)<br>> fmap f = (>>= runKleisli f)<br><br>Going the other way is tricker, because our Functor interface requires a type constructor. We'll use Id.
<br><br>> newtype Id a = Id { unId :: a }<br>> <br>> instance Monad m => Functor Id (->) (Kleisli m) where<br>> -- fmap :: (a -> b) -> Kleisli m (Id a) (Id b)<br>> fmap f = Kleisli (return . Id . f . unId)
<br><br>Finally, adjunctions between functors:<br><br>> class (Functor f morS morT, Functor g morT morS) <br>> => Adjunction f g morS morT | f g morS -> morT, f g morT -> morS<br>> where<br>> leftAdj :: morT (f a) b -> morS a (g b)
<br>> rightAdj :: morS a (g b) -> morT (f a) b<br><br>The functional dependency isn't really justified. It's there to eliminate ambiguity in the later code.<br><br>The two functors above are adjoint:<br>
<br>> instance (Monad m) => Adjunction Id m (->) (Kleisli m) where<br>> -- leftAdj :: Kleisli (Id a) b -> (a -> m b)<br>> leftAdj f = runKleisli f . Id<br>><br>> -- rightAdj :: (a -> m b) -> Kleisli (Id a) b
<br>> rightAdj f = Kleisli (f . unId)<br><br>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.<br><br>
Here are the monad operations:<br><br>> unit :: (Adjunction f g morS morT) => morS a (g(f a))<br>> unit = leftAdj id<br>> <br>> extend :: (Adjunction f g morS morT) => morS a (g(f b)) -> morS (g(f a)) (g(f b))
<br>> extend f = fmap (rightAdj f)<br><br>The monad's type constructor is the composition of g and f. Extend corresponds to (>>=) with the arguments reversed.<br><br>In our running example, unit and extend have these types:
<br><br> unit :: Monad m => a -> m (Id a)<br> extend :: Monad m => (a -> m (Id b)) -> m (Id a) -> m (Id b)<br><br>This corresponds to our original monad, only with the extra Id.<br><br>Here are the comonad operations:
<br><br>> counit :: (Adjunction f g morS morT) => morT (f(g a)) a<br>> counit = rightAdj id<br>><br>> coextend :: (Adjunction f g morS morT) => morT (f(g a)) b -> morT (f(g a)) (f(g b))<br>> coextend f = fmap (leftAdj f)
<br><br>In our running example, counit and coextend have these types:<br><br> counit :: Monad m => Kleisli m (Id (m a)) a<br> coextend :: Monad m => Kleisli m (Id (m a)) b -> Kleisli m (Id (m a)) (Id (m b))
<br><br>Thus, m is effectively a comonad in its Kleisli category.<br><br>We can tell a similar story with Comonads and CoKleisli operations, eventually reaching an adjunction like this:<br><br>> instance (Comonad w) => Adjunction w Id (CoKleisli w) (->) -- omitted
<br><br>-- <br></div></div>Dave Menendez <<a href="mailto:dave@zednenem.com">dave@zednenem.com</a>><br><<a href="http://www.eyrie.org/~zednenem/">http://www.eyrie.org/~zednenem/</a>>