Thu 22 May 2008

## Kan Extensions II: Adjunctions, Composition, Lifting

Posted by Edward Kmett under Category Theory , Comonads , Haskell , Kan Extensions , Monads[48] Comments

I want to spend some more time talking about Kan extensions, composition of Kan extensions, and the relationship between a monad and the monad generated by a monad.

But first, I want to take a moment to recall adjunctions and show how they relate to some standard (co)monads, before tying them back to Kan extensions.

**Adjunctions 101**

An adjunction between categories and consists of a pair of functors , and and a natural isomorphism:

We call the left adjoint functor, and the right adjoint functor and an adjoint pair, and write this relationship as

Borrowing a Haskell definition from Dave Menendez, an adjunction from the category of Haskell types (**Hask**) to **Hask** given by a pair of Haskell `Functor`

instances can be defined as follows, where phi is witnessed by = `leftAdjunct`

and = `rightAdjunct`

. [haddock]

class (Functor f, Functor g) => Adjunction f g | f -> g, g -> f where unit :: a -> g (f a) counit :: f (g a) -> a leftAdjunct :: (f a -> b) -> a -> g b rightAdjunct :: (a -> g b) -> f a -> b unit = leftAdjunct id counit = rightAdjunct id leftAdjunct f = fmap f . unit rightAdjunct f = counit . fmap f

**Currying and Uncurrying**

The most well known adjunction to a Haskell programmer is between the functors given by `((,)e)`

and `((->)e)`

. (Recall that you can read `((,)e)`

as `(e,)`

and `((->)e)`

as `(e->)`

; however, the latter syntax isn't valid Haskell as you aren't allowed to make `(,)`

and `(->)`

sections. We use this adjunction most every day in the form of the functions `curry`

and `uncurry`

.

curry :: ((a, b) -> c) -> a -> b -> c curry f x y = f (x,y) uncurry :: (a -> b -> c) -> (a, b) -> c uncurry f ~(x,y) = f x y

However the arguments are unfortunately slightly flipped around when we go to define this as an adjunction.

instance Adjunction ((,)e) ((->)e) where leftAdjunct f a e = f (e,a) rightAdjunct f ~(e,a) = f a e

This adjunction defines the relationship between the anonymous reader monad and the anonymous reader comonad (aka the product comonad).

**All Readers are the Same**

As an aside, if you look at the reader arrow, reader monad and reader comonad all side by side you can see that they are all basically the same thing. Kleisli arrows for the anonymous reader monad have the form `a -> e -> b`

. The Reader arrow takes the form `arr (a, e) b`

, which when `arr`

is `(->)`

this reads as `(a,e) -> b`

, which is just a curried Kleisli arrow for the Reader monad. On the other hand the reader comonad is `((,)e)`

, and its CoKleisli arrows have the form `(e,a) -> b`

. So, putting these side by side:

a -> e -> b (a , e) -> b (e , a) -> b

You can clearly see these are all the same thing!

**State and Composing Adjunctions**

Once we define functor composition:

newtype O f g a = Compose { decompose :: f (g a) } instance (Functor f, Functor g) => Functor (f `O` g) where fmap f = Compose . fmap (fmap f) . decompose

We can see that every adjunction gives rise to a monad:

instance Adjunction f g => Monad (g `O` f) where return = Compose . unit m >>= f = Compose . fmap (rightAdjunct (decompose . f)) $ decompose m

and if you happen to have a Comonad typeclass lying around, a comonad:

class Comonad w where extract :: w a -> a duplicate :: w a -> w (w a) extend :: (w a -> b) -> w a -> w b extend f = fmap f . duplicate duplicate = extend id instance Adjunction f g => Comonad (f `O` g) where extract = counit . decompose extend f = Compose . fmap (leftAdjunct (f . Compose)) . decompose

In reality, adjunction composition is of course not the only way you could form a monad by composition, so in practice a single composition constructor leads to ambiguity. Hence why in category-extras there is a base `CompF`

functor, and specialized variations for different desired instances. For simplicity, I'll stick to ``O``

here.

We can compose adjunctions, yielding an adjunction, so long as we are careful to place things in the right order:

instance (Adjunction f1 g1, Adjunction f2 g2) => Adjunction (f2 `O` f1) (g1 `O` g2) where counit = counit . fmap (counit . fmap decompose) . decompose unit = Compose . fmap (fmap Compose . unit) . unit

In fact, if we use the adjunction defined above, we can see that its just the `State`

monad!

instance MonadState e ((->)e `O` (,)e) where get = compose $ \s -> (s,s) put s = compose $ const (s,())

Not that I'd be prone to consider using that representation, but we can also see that we get the context comonad this way:

class Comonad w => ComonadContext s w | w -> s where getC :: w a -> s modifyC :: (s -> s) -> w a -> a instance ComonadContext e ((,)e `O` (->)e) where getC = fst . decompose modifyC f = uncurry (flip id . f) . decompose

**Adjunctions as Kan Extensions**

Unsurprisingly, since pretty much all of category theory comes around to being an observation about Kan extensions in the end, we can find some laws relating left- and right- Kan extensions to adjunctions.

Recall the definitions for right and left Kan extensions over **Hask**:

newtype Ran g h a = Ran { runRan :: forall b. (a -> g b) -> h b } data Lan g h a = forall b. Lan (g b -> a) (h b)

Formally, if and only if the right Kan extension exists and is preserved by . (Saunders Mac Lane, Categories for the Working Mathematician p248). We can use this in Haskell to define a natural isomorphism between `f`

and `Ran g Identity`

witnessed by `adjointToRan`

and `ranToAdjoint`

below:

adjointToRan :: Adjunction f g => f a -> Ran g Identity a adjointToRan f = Ran (\a -> Identity $ rightAdjunct a f) ranToAdjoint :: Adjunction f g => Ran g Identity a -> f a ranToAdjoint r = runIdentity (runRan r unit)

We can construct a similar natural isomorphism for the right adjoint `g`

of a `Functor`

`f`

and `Lan f Identity`

:

adjointToLan :: Adjunction f g => g a -> Lan f Identity a adjointToLan = Lan counit . Identity lanToAdjoint :: Adjunction f g => Lan f Identity a -> g a lanToAdjoint (Lan f v) = leftAdjunct f (runIdentity v)

So, with that in hand we can see that `Ran f Identity -| f -| Lan f Identity`

, presuming `Ran f Identity`

and `Lan f Identity`

exist.

**A More General Connection**

Now, the first isomorphism above can be seen as a special case of a more general law relating functor composition and Kan extensions, where `h = Identity`

in the composition below:

ranToComposedAdjoint :: Adjunction f g => Ran g h a -> (h `O` f) a ranToComposedAdjoint r = Compose (runRan r unit) composedAdjointToRan :: (Functor h, Adjunction f g) => (h `O` f) a -> Ran g h a composedAdjointToRan f = Ran (\a -> fmap (rightAdjunct a) (decompose f))

Similarly , we get the more generalize relationship for `Lan`

:

lanToComposedAdjoint :: (Functor h, Adjunction f g) => Lan f h a -> (h `O` g) a lanToComposedAdjoint (Lan f v) = Compose (fmap (leftAdjunct f) v) composedAdjointToLan :: Adjunction f g => (h `O` g) a -> Lan f h a composedAdjointToLan = Lan counit . decompose

**Composing Kan Extensions**

Using the above with the laws for composing right Kan extensions:

composeRan :: Ran f (Ran g h) a -> Ran (f `O` g) h a composeRan r = Ran (\f -> runRan (runRan r (decompose . f)) id) decomposeRan :: Functor f => Ran (f `O` g) h a -> Ran f (Ran g h) a decomposeRan r = Ran (\f -> Ran (\g -> runRan r (Compose . fmap g . f)))

or the laws for composing left Kan extensions:

composeLan :: Functor f => Lan f (Lan g h) a -> Lan (f `O` g) h a composeLan (Lan f (Lan g h)) = Lan (f . fmap g . decompose) h decomposeLan :: Lan (f `O` g) h a -> Lan f (Lan g h) a decomposeLan (Lan f h) = Lan (f . compose) (Lan id h)

can give you a lot of ways to construct monads:

**Right Kan Extension as (almost) a Monad Transformer**

You can lift many of operations from a monad m to the codensity monad of `m`

. Unfortunately, we don't have quite the right type signature for an instance of `MonadTrans`

, so we'll have to make do with our own methods:

[Edit: this has been since factored out into Control.Monad.Codensity to allow `Codensity`

to actually be an instance of `MonadTrans`

]

liftRan :: Monad m => m a -> Ran m m a liftRan m = Ran (m >>=) lowerRan :: Monad m => Ran m m a -> m a lowerRan a = runRan a return instance MonadReader r m => MonadReader r (Ran m m) where ask = liftRan ask local f m = Ran (\c -> ask >>= \r -> local f (runRan m (local (const r) . c))) instance MonadIO m => MonadIO (Ran m m) where liftIO = liftRan . liftIO instance MonadState s m => MonadState s (Ran m m) where get = liftRan get put = liftRan . put

In fact the list of things you can lift is pretty much the same as what you can lift over the `ContT`

monad transformer due to the similarity in the types. However, just because you lifted the operation into the right or left Kan extension, doesn't mean that it has the same asymptotic performance.

Similarly we can lift many comonadic operations to the `Density`

comonad of a comonad using `Lan`

.

[Edit: Refactored out into Control.Comonad.Density]

**Changing Representation**

Given a `f -| g`

, `g `O` f`

is a monad, and `Ran (g `O` f) (g `O` f)`

is the monad generated by `(g `O` f)`

, described in the previous post. We showed above that this monad can do many of the same things that the original monad could do. From there you can `decomposeRan`

to get `Ran g (Ran f (g `O` f))`

, which you can show to be yet another monad, and you can continue on from there.

Each of these monads may have different operational characteristics and performance tradeoffs. For instance the codensity monad of a monad can offer better asymptotic performance in some usage scenarios.

Similarly the left Kan extension can be used to manipulate the representation of a comonad.

All of this code is encapsulated in category-extras [docs] [darcs] as of release 0.51.0

May 23rd, 2008 at 12:06 am

Update: The current version of category-extras on hackage should now build correctly on ghc 6.8.

May 26th, 2008 at 7:23 pm

[...] Grant B. asked me to post the derivation for the right and left Kan extension formula used in previous Kan Extension posts (1,2). For that we can turn to the definition of Kan extensions in terms of ends, but first we need to take a couple of steps back to find a way to represent (co)ends in Haskell. [...]

June 5th, 2008 at 11:49 am

[...] I’ve had a few people ask me questions about Adjunctions since my recent post and a request for some more introductory material, so I figured I would take a couple of short posts to tie Adjunctions to some other concepts. [...]

June 24th, 2011 at 1:22 am

[...] arise in a subsequent post) on this blog previously, in a series of posts on Kan Extensions. [ 1, 2, [...]

June 30th, 2011 at 10:55 pm

[...] The latter few steps require identities established in my second post on Kan extensions. [...]

November 22nd, 2012 at 1:43 am

[...] , where is enriched in . Provided the above end exists, is a monad regardless of whether has an adjoint, which is the usual way one thinks of functors (in general) giving rise to [...]

September 23rd, 2022 at 4:00 am

stromectol nuzeniec https://500px.com/p/skulogovid/?view=groups...You definitely made the point!…

September 23rd, 2022 at 8:06 am

Viagra for sale https://500px.com/p/bersavahi/?view=groups...Wow all kinds of fantastic information….

September 24th, 2022 at 1:10 am

Viagra manufacturer coupon https://reallygoodemails.com/canadianpharmaceuticalsonlineusa...Good info. With thanks….

September 24th, 2022 at 4:48 am

Canadian viagra https://www.provenexpert.com/canadian-pharmaceuticals-online-usa/...You actually mentioned this very well….

September 24th, 2022 at 9:54 am

Viagra rezeptfrei https://sanangelolive.com/members/pharmaceuticals...Seriously many of awesome data….

September 26th, 2022 at 8:51 am

Viagra dosage https://melaninterest.com/user/canadian-pharmaceuticals-online/?view=likes...This is nicely put! !…

September 26th, 2022 at 12:53 pm

canada online pharmacies https://haikudeck.com/canadian-pharmaceuticals-online-personal-presentation-827506e003...You reported that really well….

September 26th, 2022 at 5:02 pm

canadian rx https://buyersguide.americanbar.org/profile/420642/0...Many thanks. I value this!…

September 27th, 2022 at 12:44 am

prescriptions from canada without https://experiment.com/users/canadianpharmacy...This is nicely said. !…

September 27th, 2022 at 10:20 am

how much does stromectol cost https://challonge.com/esapenti...Very good write ups, Thanks a lot….

September 28th, 2022 at 4:34 am

Viagra vs viagra vs levitra https://challonge.com/citlitigolf...Terrific posts. Regards….

September 28th, 2022 at 8:07 am

stromectol cvs https://order-stromectol-over-the-counter.estranky.cz/clanky/order-stromectol-over-the-counter.html...Truly many of terrific material….

September 28th, 2022 at 2:34 pm

stromectol pill https://soncheebarxu.estranky.cz/clanky/stromectol-for-head-lice.html...Amazing stuff. Thank you!…

September 29th, 2022 at 7:53 am

Viagra 20 mg best price https://dsdgbvda.zombeek.cz/...Nicely put. With thanks….

September 29th, 2022 at 2:19 pm

Buy viagra https://inflavnena.zombeek.cz/...Nicely put. Thank you!…

September 30th, 2022 at 8:36 am

Viagra from canada https://www.myscrsdirectory.com/profile/421708/0...You said it perfectly…..

September 30th, 2022 at 3:46 pm

Viagra sans ordonnance https://supplier.ihrsa.org/profile/421717/0...You’ve made your position quite effectively.!…

October 1st, 2022 at 6:08 am

Viagra cost https://wefbuyersguide.wef.org/profile/421914/0...You said that exceptionally well….

October 1st, 2022 at 10:08 am

Low cost viagra 20mg https://legalmarketplace.alanet.org/profile/421920/0...This is nicely expressed! ….

October 2nd, 2022 at 3:45 am

Viagra vs viagra vs levitra https://moaamein.nacda.com/profile/422018/0...Whoa all kinds of helpful info….

October 2nd, 2022 at 8:12 am

online pharmacy canada https://www.audiologysolutionsnetwork.org/profile/422019/0...Incredible all kinds of great tips….

October 2nd, 2022 at 11:29 am

Viagra 5 mg https://network.myscrs.org/profile/422020/0...Wow all kinds of useful data!…

October 3rd, 2022 at 5:15 am

Viagra 20mg https://sanangelolive.com/members/canadianpharmaceuticalsonlineusa...Many thanks. A good amount of write ups.

…

October 3rd, 2022 at 8:40 am

where to buy stromectol uk https://sanangelolive.com/members/girsagerea...Thanks a lot. I appreciate this!…

October 4th, 2022 at 7:23 am

Viagra canada https://www.ecosia.org/search?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Good info. Many thanks!…

October 4th, 2022 at 11:07 am

Buy viagra online https://www.mojomarketplace.com/user/Canadianpharmaceuticalsonline-EkugcJDMYH...Information effectively considered…..

October 4th, 2022 at 3:31 pm

legitimate canadian mail order pharmacies https://seedandspark.com/user/canadian-pharmaceuticals-online...You made the point….

October 5th, 2022 at 3:24 am

Viagra great britain https://www.giantbomb.com/profile/canadapharmacy/blog/canadian-pharmaceuticals-online/265652/...This is nicely said! ….

October 5th, 2022 at 12:25 pm

prescription drugs without prior prescription https://feeds.feedburner.com/bing/Canadian-pharmaceuticals-online...Incredible plenty of great data….

October 5th, 2022 at 5:12 pm

Viagra 5mg https://search.gmx.com/web/result?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Nicely put, Kudos….

October 6th, 2022 at 2:19 am

Viagra sans ordonnance https://search.seznam.cz/?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Thank you! Helpful stuff!…

October 6th, 2022 at 6:01 am

Viagra for sale https://sanangelolive.com/members/unsafiri...Effectively spoken without a doubt! ….

October 6th, 2022 at 4:14 pm

Viagra uk https://swisscows.com/en/web?query=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Awesome tips. Thank you!…

October 7th, 2022 at 3:31 am

Viagra 5mg prix https://www.dogpile.com/serp?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Awesome info. Thanks!…

October 7th, 2022 at 10:41 am

Northwest Pharmacy …Good advice. Kudos….

October 8th, 2022 at 6:40 am

Tadalafil 20 mg https://search.givewater.com/serp?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Regards, Lots of data.

…

October 8th, 2022 at 12:09 pm

Viagra vs viagra https://www.bakespace.com/members/profile/Сanadian pharmaceuticals for usa sales/1541108/…Whoa lots of excellent info!…

October 9th, 2022 at 5:17 am

canadian pharmacies online …Wow all kinds of valuable facts….

October 10th, 2022 at 7:10 am

canadian pharmacy no prescription https://headwayapp.co/canadianppharmacy-changelog...Perfectly voiced indeed. ….

October 11th, 2022 at 5:07 am

buy viagra online usa https://results.excite.com/serp?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Nicely spoken without a doubt. ….

October 11th, 2022 at 10:30 am

Viagra coupon https://canadianpharmaceuticalsonline.as.me/schedule.php...Truly a good deal of very good facts….

October 14th, 2022 at 4:54 am

Viagra 5mg https://reallygoodemails.com/orderstromectoloverthecounterusa...Superb information. Kudos!…