Sat 22 Sep 2012

## Unnatural Transformations and Quantifiers

Posted by Dan Doel under Category Theory , Haskell , Kan Extensions , Mathematics , Monads[136] Comments

Recently, a fellow in category land discovered a fact that we in Haskell land have actually known for a while (in addition to things most of us probably don't). Specifically, given two categories and , a functor , and provided some conditions in hold, there exists a monad , the codensity monad of .

In category theory, the codensity monad is given by the rather frightening expression:

Where the integral notation denotes an end, and the square brackets denote a power, which allows us to take what is essentially an exponential of the objects of by objects of , 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 monads.

It also turns out that this construction is a sort of generalization of the adjunction case. If we do have , this gives rise to a monad . But, in such a case, , so the codensity monad is the same as the monad given by the adjunction when it exists, but codensity may exist when there is no adjunction.

In Haskell, this all becomes a bit simpler (to my eyes, at least). Our category is always , which is enriched in itself, so powers are just function spaces. And all the functors we write will be rather like (objects will come from kinds we can quantify over), so ends of functors will look like `forall r. F r r`

where . Then:

newtype Codensity f a = Codensity (forall r. (a -> f r) -> f r)

As mentioned, we've known for a while that we can write a Monad instance for `Codensity f`

without caring at all about `f`

.

As for the adjunction correspondence, consider the adjunction between products and exponentials:

This gives rise to the monad , the state monad. According to the facts above, we should have that `Codensity (s ->)`

(excuse the sectioning) is the same as state, and if we look, we see:

forall r. (a -> s -> r) -> s -> r

which is the continuation passing, or Church (or Boehm-Berarducci) encoding of the monad.

Now, it's also well known that for any monad, we can construct an adjunction that gives rise to it. There are multiple ways to do this, but the most accessible in Haskell is probably via the Kleisli category. So, given a monad on , there is a category with the same objects, but where . The identity for each object is `return`

and composition of arrows is:

(f >=> g) x = f x >>= g

Our two functors are:

F a = a

F f = return . f

```
```

`U a = M a`

U f = (>>= f)

Verifying that requires only that , but this is just , which is a triviality. Now we should have that .

So, one of the simplest monads is reader, . Now, just takes objects in the Kleisli category (which are objects in ) and applies to them, so we should have `Codensity (e ->)`

is reader. But earlier we had `Codensity (e ->)`

was state. So reader is state, right?

We can actually arrive at this result another way. One of the most famous pieces of category theory is the Yoneda lemma, which states that the following correspondence holds for any functor :

This also works for any functor into and looks like:

F a ~= forall r. (a -> r) -> F r

for . But we also have our functor , which should look more like:

` U a ~= forall r. (a -> M r) -> U r`

M a ~= forall r. (a -> M r) -> M r

So, we fill in `M = (e ->)`

and get that reader is isomorphic to state, right? What's going on?

To see, we have to take a closer look at natural transformations. Given two categories and , and functors , a natural transformation is a family of maps such that for every the following diagram commutes:

The key piece is what the morphisms look like. It's well known that parametricity ensures the naturality of `t :: forall a. F a -> G a`

for , and it also works when the source is . It should also work for a category, call it , which has Haskell types as objects, but where , which is the sort of category that `newtype Endo a = Endo (a -> a)`

is a functor from. So we should be at liberty to say:

Codensity Endo a = forall r. (a -> r -> r) -> r -> r ~= [a]

However, hom types for are not merely made up of hom types on the same arguments, so naturality turns out not to be guaranteed. A functor must take a Kleisli arrow to an arrow , and transformations must commute with that mapping. So, if we look at our use of Yoneda, we are considering transformations :

Now, and . So

`t :: forall r. (a -> M r) -> M r`

will get us the right type of maps. But, the above commutative square corresponds to the condition that for all `f :: b -> M c`

:

t . (>=> f) = (>>= f) . t

So, if we have `h :: a -> M b`

, Kleisli composing it with `f`

and then feeding to `t`

is the same as feeding `h`

to `t`

and then binding the result with `f`

.

Now, if we go back to reader, we can consider the reader morphism:

f = const id :: a -> e -> e

For all relevant `m`

and `g`

, ` m >>= f = id`

and `g >=> f = f`

. So the

naturality condition here states that `t f = id`

.

Now, `t :: forall r. (a -> e -> r) -> e -> r`

. The general form of these is state actions (I've split `e -> (a, e)`

into two pieces):

t f e = f (v e) (st e) where rd :: e -> a st :: e -> e

If `f = const id`

, then:

t (const id) e = st e where st :: e -> e

But our naturality condition states that this must be the identity, so we must have `st = id`

. That is, the naturality condition selects `t`

for which the corresponding state action does not change the state, meaning it is equivalent to a reader action! Presumably the definition of an end (which involves dinaturality) enforces a similar condition, although I won't work through it, as it'd be rather more complicated.

However, we have learned a lesson. Quantifiers do not necessarily enforce (di)naturality for every category with objects of the relevant kind. It is important to look at the hom types, not just the objects .In this case, the point of failure seems to be the common, extra `s`

. Even though the type contains nautral transformations for the similar functors over , they can (in general) still manipulate the shared parameter in ways that are not natural for the domain in question.

I am unsure of how exactly one could enforce the above condition in (Haskell's) types. For instance, if we consider:

`forall r m. Monad m => (a -> m r) -> m r`

This still contains transformations of the form:

` t k = k a >> k a `

And for this to be natural would require:

` (k >=> f) a >> (k >=> f) a = (k a >> k a) >>= f `

Which is not true for all possible instantiations of f. It seems as though leaving `m`

unconstrained would be sufficient, as all that could happen is `t`

feeding a value to `k`

and yielding the result, but it seems likely to be over-restrictive.

September 23rd, 2012 at 8:26 pm

A while back I was playing with free theorems and was surprised to find types for which the free theorem wasn’t the obvious expression of (di)naturality. I was a bit perturbed. I guess I should have considered it a feature rather than a bug and investigated further.

November 16th, 2012 at 6:04 am

I actually stumbled on to this site when I was looking for something else. I found it very interesting and informative. I am doing my graduation with major as math. I would appreciate if you keep updating regularly.

December 13th, 2012 at 12:53 pm

I really don’t like maths that much but it always fascinate me like magic. This site is very informative and useful for the maths students, so please keep updating.

October 23rd, 2020 at 10:15 am

rachael…The Comonad.Reader » Unnatural Transformations and Quantifiers…

February 23rd, 2021 at 10:47 pm

psychology-essay.somee.com…The Comonad.Reader » Unnatural Transformations and Quantifiers…

February 27th, 2021 at 10:32 am

http://bnw9ts5vvtw7info.gearhostpreview.com/custom-coursework/page-305-2021-02-13.html...The Comonad.Reader » Unnatural Transformations and Quantifiers…

April 6th, 2021 at 4:00 am

fatruthngoorg.gearhostpreview.com…The Comonad.Reader » Unnatural Transformations and Quantifiers…

April 6th, 2021 at 7:14 am

reporting-essay.somee.com…The Comonad.Reader » Unnatural Transformations and Quantifiers…

May 23rd, 2021 at 2:26 am

reflectvie-essay.somee.com…The Comonad.Reader » Unnatural Transformations and Quantifiers…

May 23rd, 2021 at 11:08 pm

rs-coursework.somee.com…The Comonad.Reader » Unnatural Transformations and Quantifiers…

July 20th, 2021 at 7:19 am

lse-essay.somee.com…The Comonad.Reader » Unnatural Transformations and Quantifiers…

August 25th, 2021 at 5:44 am

itty-co-jp.somee.com…The Comonad.Reader » Unnatural Transformations and Quantifiers…

October 3rd, 2021 at 7:22 am

nerd-essays.somee.com…blog topic…

October 19th, 2021 at 9:37 pm

http://manifest-co-jp.somee.com/russian-mom/page-d25mac88ap.html...The Comonad.Reader » Unnatural Transformations and Quantifiers…

January 10th, 2022 at 11:00 am

visit website here…Find the the top personal promotional products that’s now available and at good rates now only!…

January 10th, 2022 at 5:31 pm

custom printed signage…Hire the the top promotional items that’s now available and at reasonable prices now only!…

January 10th, 2022 at 6:40 pm

water bottles with logo…Find the best personalised engraved pens currently now available in addition on sale now only!…

January 10th, 2022 at 9:05 pm

treatment for neuropathy…Get a top insipidus diabetes currently now available in addition with reasonably pricing now only!…

January 10th, 2022 at 11:59 pm

branded products…Find the best logo printed face masks that is now available and at reasonable prices now only!…

January 11th, 2022 at 1:06 am

badge reels…Get the best personal promotional products that’s now available and at reasonable prices now only!…

January 11th, 2022 at 7:39 am

Printed Gear…Find the the top promotional products that is now available and on sale now only!…

January 11th, 2022 at 2:10 pm

safety kits…Hire a top promo products suppliers that’s now available in addition at good rates now only!…

January 11th, 2022 at 8:35 pm

promotional coffee mugs…Hire the the top printed water bottles that is now available in addition on sale now only!…

January 12th, 2022 at 1:51 am

custom logo design…Get a top corporate gifts that’s now available in addition at reasonable prices now only!…

January 12th, 2022 at 4:01 pm

branded products…Hire a top embroidered hats currently now available in addition at good rates now only!…

January 12th, 2022 at 4:13 pm

Get More Info…Get the best diabetes specialist doctor that’s now available in addition at good rates now only!…

January 12th, 2022 at 10:24 pm

logo t shirts…Find a top badge holder that is now available in addition on sale now only!…

January 12th, 2022 at 11:13 pm

ortho knee…Hire the the top omaha orthopedic that is now available and at reasonable prices now only!…

January 13th, 2022 at 4:00 am

reusable face masks…Hire a top coffee mugs that’s now available and on sale now only!…

January 13th, 2022 at 6:10 am

diabetes cure type 2…Hire the the top endocrinologist diabetes that’s now available in addition at good rates now only!…

January 13th, 2022 at 11:21 am

promotional products…Hire a top branded products currently now available and at good rates now only!…

January 13th, 2022 at 5:48 pm

Learn More…Find the best custom logo design currently now available and at reasonable prices now only!…

January 13th, 2022 at 11:58 pm

engraved pens…Get the the top safety kits that’s now available and on sale now only!…

January 14th, 2022 at 2:42 am

diabetes center…Hire a top treatment for neuropathy in feet that is now available in addition at reasonable prices now only!…

January 14th, 2022 at 6:09 am

badge holder…Get a top promotional items that’s now available in addition on sale now only!…

January 14th, 2022 at 11:52 am

tote bags…Get the the top promo items that is now available in addition on sale now only!…

January 14th, 2022 at 4:13 pm

leg knee pain doctor…Hire the the top neuropathy diabetes that is now available and on sale now only!…

January 14th, 2022 at 6:06 pm

Printed Gear…Hire a top custom printed signage that’s now available and with reasonably pricing now only!…

January 14th, 2022 at 11:00 pm

see here…Get the best diabetes mellitus diagnosis that is now available and with reasonably pricing now only!…

January 15th, 2022 at 5:43 am

diabetes mellitus treatment…Hire the the top ortho doctor near me that’s now available in addition at good rates now only!…

January 15th, 2022 at 12:24 pm

nephrogenic diabetes insipidus…Get a top reverse diabetes currently now available and at reasonable prices now only!…

January 15th, 2022 at 12:48 pm

custom logo design…Get the best embroidered hats that is now available in addition on sale now only!…

January 15th, 2022 at 6:29 pm

embroidered hats…Find the best branded face masks that’s now available in addition on sale now only!…

January 16th, 2022 at 7:13 am

Printed Gear…Get the the top custom printed face masks currently now available and on sale now only!…

January 16th, 2022 at 8:35 am

my company…Find a top ketoacidosis diabetes currently now available in addition at good rates now only!…

January 16th, 2022 at 11:27 am

diabetes specialist…Get the the top knee doctor in my area that’s now available and on sale now only!…

January 16th, 2022 at 11:49 am

knee specialist near me…Find the best diabetes remision that is now available and on sale now only!…

January 16th, 2022 at 11:56 am

west omaha orthopedic clinic…Get a top how to reverse diabetes permanently that is now available in addition at good rates now only!…

January 16th, 2022 at 11:56 am

diabetes knee pain…Get a top diabetes endocrinologist that is now available and at reasonable prices now only!…

January 16th, 2022 at 12:12 pm

find more info…Hire the the top knee doctor specialist near me that is now available and with reasonably pricing now only!…

January 16th, 2022 at 12:18 pm

imp source…Procure highly amazing hotel insurance cost immediately on a best offer and gets your money flowing immediately!…

January 16th, 2022 at 12:56 pm

wholesale promotional products…Find the the top branded products that’s now available in addition on sale now only!…

January 16th, 2022 at 1:54 pm

diabetes endocrinology…Hire the best orthopedics omaha ne that is now available in addition with reasonably pricing now only!…

January 16th, 2022 at 2:04 pm

hotel insurance programs…Get going with top quality hotel insurance companies now on a best offer and gets your money flowing immediately!…

January 16th, 2022 at 3:10 pm

diabetes insipidus diagnosis…Get the best treatment for diabetes mellitus that is now available in addition with reasonably pricing now only!…

January 16th, 2022 at 4:02 pm

imprinted protective eyewear…Get the best branded products currently now available and at reasonable prices now only!…

January 16th, 2022 at 6:32 pm

click to read more…Hire a top diabetes doctor endocrinologist that’s now available and on sale now only!…

January 16th, 2022 at 6:37 pm

diabetes cure…Find a top knee doctor specialist near me that’s now available and at good rates now only!…

January 16th, 2022 at 6:38 pm

my company…Find a top ortho doctor currently now available and with reasonably pricing now only!…

January 16th, 2022 at 6:55 pm

nephrogenic diabetes insipidus…Get the the top diabetes mellitus that’s now available and on sale now only!…

January 16th, 2022 at 7:00 pm

insurance for bed and breakfast…Locate the best b&b insurance today on a best offer and gets your money flowing immediately!…

January 16th, 2022 at 8:36 pm

treatment for diabetes type 2…Hire a top neuropathy diabetes currently now available in addition with reasonably pricing now only!…

January 16th, 2022 at 9:02 pm

hospitality insurance companies…Procure top quality motel insurance companies now on a best offer and gets your business ROI immediately!…

January 16th, 2022 at 9:54 pm

ortho knee…Get a top reverse diabetes naturally that’s now available and on sale now only!…

January 16th, 2022 at 10:46 pm

visit website here…Hire the best embroidered shirts that is now available and on sale now only!…

January 16th, 2022 at 11:57 pm

hotel motel insurance companies…Locate highly amazing bed and breakfast insurance companies immediately on a best offer and gets your business ROI immediately!…

January 17th, 2022 at 12:48 am

diabetes wound care…Hire the the top endocrinologist doctor near me currently now available and at good rates now only!…

January 17th, 2022 at 12:56 am

treatment for diabetes type 1…Get a top knee doctor omaha currently now available in addition at reasonable prices now only!…

January 17th, 2022 at 1:09 am

diabetes prognosis…Get a top dka diagnosis currently now available in addition at good rates now only!…

January 17th, 2022 at 1:24 am

orthopedic doctor for knee pain…Find a top diabetes cure type 2 that’s now available in addition at good rates now only!…

January 17th, 2022 at 1:43 am

knee specialist omaha ne…Find the the top prediabetes treatments that’s now available and with reasonably pricing now only!…

January 17th, 2022 at 1:49 am

my company…Procure top quality hotel insurance cost now on a best offer and gets your money flowing immediately!…

January 17th, 2022 at 2:02 am

corporate gifts…Get the the top water bottles with logo currently now available in addition at reasonable prices now only!…

January 17th, 2022 at 4:11 am

insurance for b…Procure highly amazing insurance for event venues now on a best offer and gets your business ROI immediately!…

January 17th, 2022 at 4:13 am

knee doctor omaha ne…Get a top endocrinologist that’s now available and at reasonable prices now only!…

January 17th, 2022 at 5:38 am

custom surgical masks…Hire a top custom printed signage that’s now available in addition at reasonable prices now only!…

January 17th, 2022 at 6:48 am

hospitality insurance companies…Get going with the best motel insurance program today on a best offer and gets your business ROI immediately!…

January 17th, 2022 at 7:45 am

diabetes treatment…Find the best management of diabetes that’s now available and with reasonably pricing now only!…

January 17th, 2022 at 7:48 am

my review here…Get the best orthopedic doctors omaha ne that’s now available and at reasonable prices now only!…

January 17th, 2022 at 7:55 am

type 1 diabetes treatment…Hire a top knee doctors in omaha ne that’s now available and at reasonable prices now only!…

January 17th, 2022 at 8:12 am

knee doctor omaha ne…Hire the best diabetes endocrinology that’s now available in addition with reasonably pricing now only!…

January 17th, 2022 at 8:15 am

diabetes physical exam…Find the the top how to reverse diabetes naturally in 30 days that is now available and at good rates now only!…

January 17th, 2022 at 8:33 am

ortho knee doctors near me…Hire the the top diabetes prevention that’s now available and with reasonably pricing now only!…

January 17th, 2022 at 8:37 am

imprinted protective eyewear…Hire a top wholesale promotional products that is now available and at reasonable prices now only!…

January 17th, 2022 at 8:38 am

hotel insurance requirements…Procure top quality lodge insurance today on a best offer and gets your business ROI immediately!…

January 17th, 2022 at 10:18 am

diabetes doctor endocrinologist…Hire the best knee specialist omaha currently now available and on sale now only!…

January 17th, 2022 at 10:49 am

diabetes center…Find the best best diabetes doctor that’s now available in addition on sale now only!…

January 17th, 2022 at 11:01 am

insurance for lodges…https://community.plus.net/t5/user/viewprofilepage/user-id/109015innkeepers liability insurance…

January 17th, 2022 at 11:18 am

bed and breakfast insurance…Locate top quality hospitality insurance companies immediately on a best offer and gets your money flowing immediately!…

January 17th, 2022 at 12:26 pm

custom printed face masks…Get the best logo printed face masks that is now available in addition on sale now only!…

January 17th, 2022 at 1:35 pm

motel insurance brokers…Locate highly amazing hospitality insurance companies today on a best offer and gets your business ROI immediately!…

January 17th, 2022 at 2:32 pm

treatment for diabetes mellitus…Hire a top diabetes mellitus treatment that’s now available and at reasonable prices now only!…

January 17th, 2022 at 2:57 pm

endocrinologist omaha…Get the best diabetes lab tests that’s now available in addition at good rates now only!…

January 17th, 2022 at 2:59 pm

insipidus diabetes…Find the best diabetes endocrinologist that’s now available and at reasonable prices now only!…

January 17th, 2022 at 3:02 pm

ketoacidosis diabetes…Get the best knee doctor specialist near me currently now available in addition with reasonably pricing now only!…

January 17th, 2022 at 3:20 pm

diabetes cure type 2…Hire the best knee doctors in omaha ne that’s now available and with reasonably pricing now only!…

January 17th, 2022 at 3:24 pm

bed and breakfast insurance…Locate the best bed and breakfast insurance rates today on a best offer and gets your business ROI immediately!…

January 17th, 2022 at 5:05 pm

ortho doctor near me…Get the the top diabetes doctor specialist currently now available and at reasonable prices now only!…

January 17th, 2022 at 5:29 pm

knee joint pain doctor…Find the best neuropathy diabetes that’s now available in addition at good rates now only!…

January 17th, 2022 at 6:00 pm

hotel insurance programs…https://www.gamedev.net/bandbinsurance/about/bed & breakfast insurance…

January 17th, 2022 at 6:20 pm

treatment for neuropathy in feet…Get a top type 2 diabetes treatment that is now available and at reasonable prices now only!…

January 17th, 2022 at 6:22 pm

bed & breakfast insurance…Procure top quality hotel insurance companies now on a best offer and gets your money flowing immediately!…

January 17th, 2022 at 8:25 pm

insurance for event space…Locate the best bed & breakfast insurance immediately on a best offer and gets your money flowing immediately!…

January 17th, 2022 at 9:16 pm

knee pain…Find the best diabetes center that is now available and at reasonable prices now only!…

January 17th, 2022 at 9:20 pm

diabetes doctor endocrinologist…Get the best knee pain doctor that’s now available in addition at good rates now only!…

January 17th, 2022 at 9:35 pm

orthopedic doctors in omaha…Find the best knee pain doctor near me that is now available in addition with reasonably pricing now only!…

January 17th, 2022 at 9:39 pm

personalised engraved pens…Hire the the top imprinted protective eyewear currently now available and at good rates now only!…

January 17th, 2022 at 10:01 pm

treatment for nephrogenic diabetes insipidus…Get a top treatment for nephrogenic diabetes insipidus currently now available in addition at good rates now only!…

January 17th, 2022 at 10:05 pm

diabetes specialist…Find the the top how to reverse diabetes naturally in 30 days that is now available in addition at good rates now only!…

January 17th, 2022 at 10:09 pm

bed and breakfast insurance rates…Procure highly amazing insurance bed and breakfast today on a best offer and gets your money flowing immediately!…

January 17th, 2022 at 11:51 pm

treatment for diabetes insipidus…Get the best orthopedic doctors omaha ne that is now available in addition at good rates now only!…

January 18th, 2022 at 1:15 am

hotel insurance cost…https://www.ourboox.com/i-am/b-and-b-insurance/great post to read…

January 18th, 2022 at 1:17 am

click site…Hire the best type 1 diabetes treatment that is now available in addition on sale now only!…

January 18th, 2022 at 2:11 am

logo face masks…Get a top logo face masks that’s now available and at reasonable prices now only!…

January 18th, 2022 at 4:27 am

see it here…Find the the top diabetes mellitus diagnosis that’s now available in addition at reasonable prices now only!…

January 18th, 2022 at 4:29 am

knee pain doctor specialist…Find a top endocrinologist omaha currently now available in addition on sale now only!…

January 18th, 2022 at 4:31 am

treatment for diabetes type 1…Find the best nebraska orthopedic omaha that’s now available in addition at good rates now only!…

January 18th, 2022 at 4:36 am

personal promotional products…Find the best luggage tags that is now available in addition at good rates now only!…

January 18th, 2022 at 4:47 am

diabetes center…Hire the best knee doctor omaha ne that’s now available in addition with reasonably pricing now only!…

January 18th, 2022 at 5:15 am

knee doctor omaha…Find the the top how to reverse diabetes naturally in 30 days that’s now available in addition on sale now only!…

January 18th, 2022 at 5:29 am

diabetes cure type 2…Get the the top knee doctors that is now available in addition at reasonable prices now only!…

January 18th, 2022 at 7:07 am

diabetes doctor endocrinologist…Get the the top treatment for nephrogenic diabetes insipidus that is now available in addition on sale now only!…

January 18th, 2022 at 8:29 am

diabetes cure type 2…Hire the best diabetes wound healing currently now available and at good rates now only!…

January 18th, 2022 at 8:46 am

bed & breakfast insurance…https://www.algebra.com/tutors/aboutme.mpl?userid=bandbinsurancehospitality insurance…

January 18th, 2022 at 9:05 am

Learn More…Find a top promo items currently now available and at reasonable prices now only!…

January 18th, 2022 at 11:12 am

insurance for bed and breakfast…Procure top quality insurance for lodges today on a best offer and creates efficiency for you immediately!…

January 18th, 2022 at 11:25 am

best diabetes doctor near me…Get a top orthopedic doctor that is now available and on sale now only!…

January 18th, 2022 at 11:41 am

see here…Hire the the top diabetes insipidus diagnosis that is now available in addition on sale now only!…

January 18th, 2022 at 11:42 am

diabetes endocrinology…Get the best endocrinologist diabetes that’s now available and on sale now only!…

January 18th, 2022 at 12:28 pm

ortho knee surgery…Get the best knee pain doctor near me that’s now available in addition at reasonable prices now only!…

January 18th, 2022 at 12:33 pm

this page…Procure highly amazing lodge insurance now on a best offer and creates efficiency for you immediately!…

January 18th, 2022 at 1:02 pm

gestational diabetes…Hire a top orthopedic doctor that’s now available in addition at good rates now only!…

January 18th, 2022 at 3:05 pm

gestational diabetes treatment…Get the the top diabetes cure that is now available and at good rates now only!…

January 18th, 2022 at 3:42 pm

diabetes doctor specialist…Get a top treatment for diabetes insipidus currently now available in addition at good rates now only!…

January 18th, 2022 at 4:02 pm

engraved pens…Find a top luggage tags currently now available and on sale now only!…

January 18th, 2022 at 4:37 pm

ski lodge insurance…Get going with the best hospitality insurance programs immediately on a best offer and gets your business ROI immediately!…