Wed 30 Apr 2008

## Deriving Strength from Laziness

Posted by Edward Kmett under Category Theory , Comonads , Haskell , Monads[58] Comments

No, this isn't some uplifting piece about deriving courage from sloth in the face of adversity.

What I want to talk about is **monadic** strength.

Transcribing the definition from category theory into Haskell we find that a strong monad is a functor such that there exists a morphism:

with a couple of conditions on it that I'll get to later.

Currying that to get something that feels more natural to a Haskell programmer we get:

mstrength :: Monad m => m a -> b -> m (a,b)

Pardo provided us with a nice definition for that in Towards merging recursion and comonads:

mstrength ma b = ma >>= (\\a -> return (a,b))

which we can rewrite by pulling the return out of the function:

mstrength' ma b = ma >>= return . (\\a -> (a,b))

Now, one of the nice monad laws we have says that if your Monad is a Functor, which it should be, then:

fmap f xs == xs >>= return . f

This law is what gives us the definition for liftM modulo the do-sugar used when writing it.

This lets us write:

strength :: Functor f => f a -> b -> f (a,b) strength fa b = fmap (\\a -> (a,b)) fa

Then by the monad laws any definition for Monad for this Functor must be strong in the sense that if it was made into a monad, this strength function would be a valid strength for the monad.

So we get the interesting observation that all functors in Haskell are 'strong'. Lets look at a couple:

**Example ((,)c)**

instance Functor ((,)c) where fmap f ~(a,b) = (a,f b)

The above may be familiar as the reader comonad, or as the functor induced by the (,) Bifunctor.

What is the meaning of its strength?

strength{(,)c} :: ((c,a),b) -> (c,(a,b))

Well, thats just the associative law for the (,) bifunctor.

**Example (Either a)**

What about the built-in functor instance for (Either a)?

instance Functor (Either a) where fmap f (Left a) = Left a fmap f (Right b) = Right (f b)

strength{Either c} :: (Either c a, b) -> Either c (a,b)

This strength gives us a (slightly weak) form of distributive law for sums over products in Haskell.

Having strength lets us know that if we have a functor of a's I can go through it and just drop in b's in along side each of the a's.

The show is over. Everyone can go home.

Not *quite*. What about comonadic **costrength**?

with a couple of laws we can ignore for the moment.

Since we can derive strength for all Functors in Haskell, we'd think at first

that we could do the same for costrength, after all most constructions work out that way when you can

construct one, its dual usually means something interesting and works out fine.

Here I'll introduce a typeclass, foreshadowing that this probably won't go so smoothly:

class Functor w => Costrong w where costrength :: w (Either a b) -> Either (w a) b

Unfortunately costrength cannot be derived for every functor in Haskell. Lets look at what it does and see why.

With costrength, given a data structure decorated at each point with either an 'a' or a 'b' I can walk the entire structure and if I found a's everywhere then I know I have 'a's in every position, so I can strengthen the type to say that it just contains 'a's. Otherwise I found a b, so I'll give you one of the b's I found. This requires that I'm somehow able to decide if the structure contains b's anywhere and constructively give you one if it does.

Lets find a functor that you can't do this to.

instance Functor ((->)e) where fmap = (.)

An instance of costrength for (->) e,

costrength{(->)e} :: (e -> Either a b) -> Either (e -> a) b

would be equivalent to deciding that the function returns only Left's for all inputs.

Epic failure; functions are out.

Now, if we restrict ourselves to polynomial functors, we can try again, but what about infinite data structures?

```
data Stream a = a < : Stream a
```

Lets define the following stream comparison function:

eqstream :: Eq a => Stream a -> Stream a -> Stream (Either () ()) eqstream (a < : as) (b <: bs) = c <: eqstream as bs where c = if a == b then Right () else Left ()

Deciding equality of streams is complete , so this would imply that we have an oracle for the halting problem!

Ok, so infinite data structures are out.

This rules out 'coinductive' structures in general, but inductive structures are fine.

So what is in?

In Scheme you can define costrength with a the use of call-cc, which I'll leave as an exercise to the reader.

But, you can't use fmap to do that in Haskell, because call-cc passing around the current continuation is a form of monadic side effect. You could use the old Data.FunctorM and a Cont monad, but we like to think in terms of Data.Traversable today.

Unfortunately 'Either' isn't a Haskell monad in general because of some noise about trying to support 'fail', but if we define a less restrictive Either monad than the one in Control.Monad.Error, like the following:

instance Monad (Either a) where return = Right Left a >>= k = Left a Right a >>= k = k a

then using the version of mapM in Data.Traversable,

mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)

if we look at this specialized to 'id',

mapM{Either a} id :: Traversable f => f (Either a b) -> Either a (f b)

we have almost has the right type. (In fact the above is probably a more natural signature for costrength in Haskell, because it is a distributive law for any Traversable functor f over (Either a). In fact mapM id (also known as sequence) is a distributive law for a traversable functor over any monad.

If we note the fact that sums are symmetric:

class Symmetric p where swap :: p a b -> p b a instance Symmetric Either where swap (Left a) = Right a swap (Right a) = Left a

then:

costrength :: Traversable f => f (Either a b) = Either (f a) b costrength = swap . mapM swap

The ability to define strength in general came from the fact that we were lazy enough that 'strength' doesn't try to evaluate the potentially infinite structure (there are little hidden functions all over the place in the form of thunks). The trade off is that we aren't 'strict' enough for 'costrength' to be definable in general.

A couple of uses for costrength:

**Example (Either c)**

costrength {Either c} :: Either c (Either a b) = Either (Either c a) b

is just the coassociative law for Either.

**Example ((,)c)**

costrength {(,)c} :: (c, Either a b) = Either (c,a) b

lets us distribute sums over products another way.

**Example []**

Finally,

costrength {[]} :: [Either a b] -> Either [a] b

lets us pretend that we can solve the stream problem above, but it just bottoms out if you apply it to an infinite list.

In short, in Haskell, every Functor is strong and every Traversable Functor is (something like) costrong.

[Edit: Dan Doel pointed out that instead of mapM id you could use sequence]

[Edit: @blaisorblade pointed out that this should really be using traverse these days]

[Edit: This isn't quite costrength. Why? It fails the reverse of the second strength law. In reality we need to limit ourselves further -- to left adjoints.]

May 1st, 2008 at 4:36 am

One of the Estonians’ comonadic papers talk about zippability: w a -> w b -> w (a,b).

I definitely like to know what you thought about that concept and its dual, if any.

May 4th, 2008 at 10:01 pm

[...] Kefer asked a question in the comments of my post about (co)monadic (co)strength about Uustalu and Vene’s ComonadZip class from p157 of The Essence of Dataflow Programming. The class in question is: [...]

May 18th, 2008 at 11:33 pm

A follow-up in case anyone cares about this stuff. A lot can be said about “the meaning of strength:”

http://pages.cpsc.ucalgary.ca/~robin/Theses/Strength.ps.gz

May 19th, 2008 at 9:37 pm

[...] So can we convert between an apomorphism and an Elgot algebra? For a somewhat circuitous path to that answer lets recall the definition of strength from my post a couple of weeks ago. Flipping the arguments and direction of application for strength to simplify what is coming we get: [...]

April 30th, 2011 at 9:28 pm

Sorry to only be responding to this three years later, but:

1) Shouldn’t the costrength case have the added constraint (Monoid e), if only for conformity to its Comonadic form?

2) Is there a way we can exploit the (Monoid e) constraint to give us a meaningful result for costrength?

May 1st, 2011 at 3:31 am

BMeph: 1.) nah, the costrength used here was derived from relaxing the notion from a comonad to a functor in the same way that strength was weakened from mstrength.

2.) Even with some random Monoid constraint on e it wouldn’t give you the power to enumerate all possible values of e, to complete the costrength.

July 18th, 2014 at 12:48 pm

Since this is linked from profunctor’s docs, I’ll ask a question after all this time. Shouldn’t costrength use traverse rather than mapM?

GHCi then gives:

swap . traverse swap

:: (Applicative (p a), Traversable t, Symmetric p) =>

t (p b a) -> p (t b) a

and we can instantiate p with Either (and clean up a bit) to get:

swap . traverse swap

:: (Traversable t) =>

t (Either a b) -> Either (t a) b

August 1st, 2014 at 3:47 am

@blaisorblade:

Even worse than that:

costrength as defined here is actually wrong!

I need to spend some time writing that up, but if you check the dual of the strength laws the second one fails for this form!

March 2nd, 2016 at 8:15 am

Just some typo:

In Scheme you can define costrength with a the use of call-cc, which I’ll leave as an exercise to the reader.

I am also having these, not sure if it is mine or your problem:

mstrength ma b = ma >>= (\\a -> return (a,b))

mstrength’ ma b = ma >>= return . (\\a -> (a,b))

strength fa b = fmap (\\a -> (a,b)) fa

using firefox

June 3rd, 2017 at 1:11 am

The Comonad.Reader …[...]I am now not sure where you are getting your info, however good topic.[...]…

September 23rd, 2022 at 5:47 am

stromectol pharmacokinetics https://500px.com/p/skulogovid/?view=groups...You actually mentioned that effectively….

September 23rd, 2022 at 9:46 am

Canadian viagra https://500px.com/p/bersavahi/?view=groups...Many thanks, Plenty of data.

…

September 24th, 2022 at 2:55 am

canadian pharmacy world https://reallygoodemails.com/canadianpharmaceuticalsonlineusa...With thanks. Good stuff….

September 24th, 2022 at 6:28 am

Viagra or viagra https://www.provenexpert.com/canadian-pharmaceuticals-online-usa/...With thanks! A good amount of content!

…

September 24th, 2022 at 11:34 am

Viagra kaufen https://sanangelolive.com/members/pharmaceuticals...Amazing data. With thanks!…

September 26th, 2022 at 10:36 am

Viagra 5 mg https://melaninterest.com/user/canadian-pharmaceuticals-online/?view=likes...You’ve made the point….

September 26th, 2022 at 2:36 pm

Generic viagra https://haikudeck.com/canadian-pharmaceuticals-online-personal-presentation-827506e003...Regards. An abundance of knowledge!

…

September 26th, 2022 at 6:44 pm

Viagra sans ordonnance https://buyersguide.americanbar.org/profile/420642/0...Thanks a lot. I enjoy this!…

September 27th, 2022 at 2:24 am

Viagra 20mg https://experiment.com/users/canadianpharmacy...You have made your point….

September 27th, 2022 at 8:21 am

Viagra generika https://slides.com/canadianpharmaceuticalsonline...Fantastic info. Regards!…

September 27th, 2022 at 12:04 pm

buy generic stromectol https://challonge.com/esapenti...Wow a lot of valuable information….

September 27th, 2022 at 4:29 pm

Viagra prices https://challonge.com/gotsembpertvil...Lovely facts, Thank you!…

September 28th, 2022 at 6:10 am

Viagra 5 mg https://challonge.com/citlitigolf...Thanks a lot, Awesome stuff….

September 28th, 2022 at 4:10 pm

where to buy stromectol uk https://soncheebarxu.estranky.cz/clanky/stromectol-for-head-lice.html...Very good forum posts. With thanks….

September 29th, 2022 at 5:41 am

stromectol reviews https://lehyriwor.estranky.sk/clanky/stromectol-cream.html...Fantastic information, Thank you!…

September 29th, 2022 at 9:28 am

stromectol india https://dsdgbvda.zombeek.cz/...Cheers! Very good stuff!…

September 29th, 2022 at 3:57 pm

stromectol medicine https://inflavnena.zombeek.cz/...Lovely facts. Kudos….

September 30th, 2022 at 10:11 am

Viagra uk https://www.myscrsdirectory.com/profile/421708/0...Nicely put. Thanks a lot….

September 30th, 2022 at 5:25 pm

Viagra great britain https://supplier.ihrsa.org/profile/421717/0...Many thanks! Plenty of data!

…

October 1st, 2022 at 7:44 am

Viagra vs viagra https://wefbuyersguide.wef.org/profile/421914/0...Valuable data. Thanks a lot!…

October 1st, 2022 at 11:48 am

online pharmacy canada https://legalmarketplace.alanet.org/profile/421920/0...Amazing data. Many thanks!…

October 2nd, 2022 at 5:22 am

Viagra 20 mg https://moaamein.nacda.com/profile/422018/0...You made your point!…

October 2nd, 2022 at 9:47 am

Viagra 5mg https://www.audiologysolutionsnetwork.org/profile/422019/0...Wow loads of beneficial material!…

October 2nd, 2022 at 1:06 pm

Canadian Pharmacies Shipping to USA https://network.myscrs.org/profile/422020/0...Terrific information, Many thanks!…

October 3rd, 2022 at 6:50 am

Buy viagra https://sanangelolive.com/members/canadianpharmaceuticalsonlineusa...Fantastic advice. With thanks….

October 3rd, 2022 at 10:20 am

Viagra manufacturer coupon https://sanangelolive.com/members/girsagerea...You actually suggested it exceptionally well….

October 4th, 2022 at 9:12 am

best canadian pharmacies online https://www.ecosia.org/search?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…With thanks. Numerous forum posts.

…

October 4th, 2022 at 1:23 pm

Viagra for daily use https://www.mojomarketplace.com/user/Canadianpharmaceuticalsonline-EkugcJDMYH...You’ve made your position extremely well!….

October 4th, 2022 at 5:20 pm

Viagra coupon https://seedandspark.com/user/canadian-pharmaceuticals-online...Incredible quite a lot of great tips….

October 5th, 2022 at 10:22 am

canadian pharmacy https://www.giantbomb.com/profile/canadapharmacy/blog/canadian-pharmaceuticals-online/265652/...Thanks a lot, An abundance of write ups!

…

October 5th, 2022 at 6:58 pm

Buy viagra online https://search.gmx.com/web/result?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Appreciate it! Loads of write ups!

…

October 5th, 2022 at 10:45 pm

dedicated server arch…The Comonad.Reader » Deriving Strength from Laziness…

October 6th, 2022 at 4:03 am

highest rated canadian pharmacies https://search.seznam.cz/?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Nicely put. Thanks a lot!…

October 6th, 2022 at 7:47 am

Viagra levitra https://sanangelolive.com/members/unsafiri...Many thanks. Lots of write ups!

…

October 6th, 2022 at 11:59 am

online pharmacy canada …Thanks. Numerous facts.

…

October 6th, 2022 at 5:56 pm

Viagra coupon https://swisscows.com/en/web?query=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Helpful info. Many thanks….

October 7th, 2022 at 5:29 am

buy viagra usa https://www.dogpile.com/serp?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Nicely put, Thank you!…

October 7th, 2022 at 12:39 pm

Viagra pills …Cheers, Ample facts!

…

October 8th, 2022 at 5:00 pm

buy lamisil…The Comonad.Reader » Deriving Strength from Laziness…

October 8th, 2022 at 9:19 pm

dedicated server advantages…The Comonad.Reader » Deriving Strength from Laziness…

October 9th, 2022 at 7:09 am

canadadrugs …Many thanks! A good amount of posts!

…

October 9th, 2022 at 12:16 pm

Viagra 5mg https://results.excite.com/serp?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…You suggested that perfectly….

October 9th, 2022 at 4:48 pm

Viagra canada https://www.infospace.com/serp?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…With thanks, Lots of content!

…

October 10th, 2022 at 9:04 am

canadian pharmacies https://headwayapp.co/canadianppharmacy-changelog...Nicely put, Thank you!…

October 11th, 2022 at 7:05 am

Viagra dosage https://results.excite.com/serp?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…You actually stated it wonderfully….

October 11th, 2022 at 12:29 pm

Viagra 5mg prix https://canadianpharmaceuticalsonline.as.me/schedule.php...Many thanks! Useful information….

October 13th, 2022 at 2:20 pm

Viagra pills https://feeds.feedburner.com/bing/stromectolnoprescription...Superb information. Regards….

October 14th, 2022 at 6:44 am

Online viagra https://reallygoodemails.com/orderstromectoloverthecounterusa...Nicely put. Thanks!…