Wed 30 Apr 2008
Deriving Strength from Laziness
Posted by Edward Kmett under Category Theory , Comonads , Haskell , Monads[93] 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.[...]…
February 23rd, 2019 at 8:18 am
instead of:
mstrength :: Monad m => m a -> b -> m (a,b)
why not the even more natural:
mstrength :: Monad m => m a -> b -> (a -> b -> c) -> m c
May 25th, 2019 at 1:22 am
Daforumanau.Net…
The Comonad.Reader …
May 3rd, 2022 at 7:19 am
buy cialis https://online-pharmacies0.yolasite.com/...
Kudos, Valuable information….
May 3rd, 2022 at 2:35 pm
canadian cialis https://6270e49a4db60.site123.me/blog/the-untold-secret-to-mastering-aspirin-in-just-7-days-1...
Incredible a good deal of fantastic advice!…
May 4th, 2022 at 8:58 am
canadian pharmacy online https://deiun.flazio.com/...
Nicely put, Appreciate it….
May 4th, 2022 at 5:31 pm
generic for cialis https://kertyun.flazio.com/...
You said it nicely…..
May 5th, 2022 at 7:00 am
canadian pharmacy online https://kerntyas.gonevis.com/the-mafia-guide-to-online-pharmacies/...
You made your stand extremely nicely.!…
May 5th, 2022 at 12:55 pm
cialis without a doctor’s prescription https://kerbnt.flazio.com/...
Point well utilized!….
May 5th, 2022 at 7:02 pm
cialis without a doctor’s prescription http://nanos.jp/jmp?url=http://cialisonlinei.com/...
You said it perfectly.!…
May 6th, 2022 at 5:36 am
online pharmacy http://ime.nu/cialisonlinei.com...
Truly loads of wonderful info!…
May 6th, 2022 at 7:26 am
Hostings Discounts…
I found a great……
May 6th, 2022 at 11:01 am
cialis generico https://womed7.wixsite.com/pharmacy-online/post/new-ideas-into-canada-pharmacies-never-before-revealed...
Wonderful material. Thank you!…
May 7th, 2022 at 5:18 am
Hostings Coupons…
I found a great……
May 7th, 2022 at 9:31 am
cialis from canada https://kerntyast.flazio.com/...
Truly a lot of superb material!…
May 7th, 2022 at 4:59 pm
canadian government approved pharmacies https://sekyuna.gonevis.com/three-step-guidelines-for-online-pharmacies/...
Whoa many of helpful tips….
May 8th, 2022 at 7:37 am
online prescriptions without a doctor https://gewrt.usluga.me/...
Seriously all kinds of useful knowledge….
May 8th, 2022 at 2:16 pm
Get Hostings Coupons…
I found a great……
May 9th, 2022 at 7:11 am
HostingsCoupons…
I found a great……
May 9th, 2022 at 11:09 am
pharmacy canada https://pharmacy-online.webflow.io/...
Superb knowledge. Thanks a lot….
May 9th, 2022 at 5:34 pm
cialis generico https://canadian-pharmacy.webflow.io/...
You said it very well…..
May 10th, 2022 at 3:42 am
cialis tablets https://site273035107.fo.team/...
Truly tons of wonderful information….
May 10th, 2022 at 12:04 pm
buy cialis without a doctor’s prescription https://site656670376.fo.team/...
Very good content. With thanks….
May 10th, 2022 at 10:16 pm
generic for cialis https://site561571227.fo.team/...
Great facts, Kudos….
May 11th, 2022 at 4:24 am
cialis canada https://site102906154.fo.team/...
You actually reported it adequately….
May 11th, 2022 at 10:21 am
cialis generico https://hekluy.ucraft.site/...
Thanks! I value this….
May 11th, 2022 at 11:29 am
Hostings Coupons Discounts…
I found a great……
May 11th, 2022 at 8:51 pm
tadalafil 10 mg https://kawsear.fwscheckout.com/...
Superb info, Thanks….
May 13th, 2022 at 11:18 am
cialis 5mg prix https://hertnsd.nethouse.ru/...
Kudos. Terrific information!…
May 14th, 2022 at 11:15 am
online prescriptions without a doctor https://uertbx.livejournal.com/402.html...
You actually reported that superbly….
May 14th, 2022 at 5:31 pm
canadian pharmacy world https://lwerts.livejournal.com/276.html...
Thanks a lot! Ample tips!
…
May 15th, 2022 at 9:34 am
list of reputable canadian pharmacies https://avuiom.sellfy.store/...
Very good forum posts, Kudos….
May 15th, 2022 at 9:34 pm
canadian pharmacies without an rx https://pharmacies.bigcartel.com/...
Thanks a lot. Loads of information.
…
May 16th, 2022 at 11:01 am
Cheap cialis https://kwersd.mystrikingly.com/...
You actually reported this really well….
May 16th, 2022 at 5:00 pm
buy generic cialis https://gewsd.estranky.sk/clanky/drugstore-online.html...
You have made your stand very clearly.!…
May 17th, 2022 at 3:19 am
generic cialis https://kqwsh.wordpress.com/2022/05/16/what-everybody-else-does-when-it-comes-to-online-pharmacies/...
Nicely put. Appreciate it!…
May 17th, 2022 at 1:23 pm
online canadian pharmacies http://site592154748.fo.team/...
Regards! Very good information….
May 18th, 2022 at 6:34 am
buy viagra now https://lasert.gonevis.com/recommended-canadian-pharmacies-2/...
Fantastic write ups, Thanks!…
May 18th, 2022 at 2:45 pm
buy cialis online http://aonubs.website2.me/...
Amazing facts. Appreciate it!…
May 20th, 2022 at 11:16 am
cialis tablets australia https://dkyubn.bizwebs.com/...
Thanks! I appreciate this!…
May 21st, 2022 at 4:23 am
canada drug pharmacy https://asebg.bigcartel.com/canadian-pharmacy...
Excellent write ups. Kudos!…
May 21st, 2022 at 3:41 pm
Buy Fast Private Proxies…
I found a great……
May 22nd, 2022 at 6:46 am
Private Proxies…
I found a great……
May 22nd, 2022 at 7:41 am
tadalafil 10 mg https://medicine-online.estranky.sk/clanky/understand-covid-19-and-know-the-tricks-to-avoid-it-from-spreading—–medical-services.html...
You reported this well!…
May 23rd, 2022 at 7:57 am
cialis https://kertvbs.webgarden.com/...
Superb write ups. Regards….
May 23rd, 2022 at 5:59 pm
Generic cialis tadalafil https://disvaiza.mystrikingly.com/...
Thanks, Good information….
May 25th, 2022 at 8:24 am
cialis purchase online without prescription https://swenqw.company.site/...
Reliable data. Appreciate it….
May 26th, 2022 at 10:34 am
medication without a doctors prescription https://kewburet.wordpress.com/2022/04/27/how-to-keep-your-workers-healthy-during-covid-19-health-regulations/...
Awesome facts, Many thanks….
May 26th, 2022 at 4:53 pm
cialis lowest price https://kaswesa.nethouse.ru/...
Fine posts. Thank you!…
May 27th, 2022 at 1:16 pm
canada pharmacies online prescriptions https://628f789e5ce03.site123.me/blog/what-everybody-else-does-when-it-comes-to-canadian-pharmacies...
Kudos. Helpful stuff!…
May 28th, 2022 at 11:15 am
Dedicated Proxies…
I found a great……
May 30th, 2022 at 4:29 pm
seo lists…
The Comonad.Reader » Deriving Strength from Laziness…
June 1st, 2022 at 11:53 am
canada pharmacies online https://canadian-pharmaceutical.webflow.io/...
Information well considered!!…
June 1st, 2022 at 6:43 pm
tadalafil http://pamelaliggins.website2.me/...
You actually revealed it very well….
June 3rd, 2022 at 10:31 am
aid for Ukraine…
The Comonad.Reader » Deriving Strength from Laziness…
June 3rd, 2022 at 12:07 pm
viagra canada http://pharmacy.prodact.site/...
You revealed this really well!…
June 4th, 2022 at 12:27 pm
tadalafil 10 mg https://hub.docker.com/r/gserv/pharmacies...
Nicely put. Thanks a lot….
June 5th, 2022 at 1:19 pm
best canadian pharmacy https://hertb.mystrikingly.com/...
Fine write ups. Thank you….
June 6th, 2022 at 8:23 am
cialis from canada https://kedmnx.estranky.sk/clanky/online-medicine-tablets-shopping-the-best-manner.html...
Thank you. I appreciate this!…
June 6th, 2022 at 5:04 pm
cialis 20mg prix en pharmacie https://selera.mystrikingly.com/...
Good posts. Cheers!…
June 7th, 2022 at 7:40 am
top rated online canadian pharmacies https://ksorvb.estranky.sk/clanky/why-online-pharmacies-is-good-friend-to-small-business.html...
Thanks a lot, A lot of content!
…
June 8th, 2022 at 7:54 am
tadalafil 10 mg https://gevcaf.estranky.cz/clanky/safe-canadian-online-pharmacies.html...
You suggested that wonderfully….
June 10th, 2022 at 8:46 am
generic cialis https://kwervb.estranky.cz/clanky/canadian-government-approved-pharmacies.html...
Nicely put. Cheers….
June 12th, 2022 at 10:31 am
cialis prices https://sdtyli.zombeek.cz...
You said this well….
June 12th, 2022 at 2:21 pm
Buy Private Proxies…
I found a great……
June 13th, 2022 at 5:16 am
cialis https://kwsde.zombeek.cz/...
Many thanks. An abundance of data!
…
June 14th, 2022 at 11:26 am
cialis generico https://heklrs.wordpress.com/2022/06/14/canadian-government-approved-pharmacies/...
Useful postings. Kudos….
June 15th, 2022 at 8:50 am
cialis 20mg prix en pharmacie https://iercvsw.wordpress.com/2022/06/14/canadian-pharmacies-the-fitting-manner/...
Really lots of good info!…
June 18th, 2022 at 9:32 pm
Garret Spotwood…
I found a great……
June 21st, 2022 at 9:25 am
Cheap cialis https://site955305180.fo.team/...
Nicely put, Thanks a lot!…
June 22nd, 2022 at 9:18 am
1insurance…
…
June 22nd, 2022 at 10:00 am
cialis generico online http://site841934642.fo.team/...
You said it adequately…..
June 22nd, 2022 at 11:11 am
how To find an escort agency…
The Comonad.Reader » Deriving Strength from Laziness…
June 22nd, 2022 at 9:25 pm
buy cialis without a doctor’s prescription https://62b2f636ecec4.site123.me/blog/canadian-pharmaceuticals-online...
Valuable forum posts. With thanks!…
June 23rd, 2022 at 7:43 am
buy viagra usa https://62b2ffff12831.site123.me/blog/canadian-pharmaceuticals-for-usa-sales...
Cheers, A lot of advice.
…
June 27th, 2022 at 7:17 pm
Buy Proxies…
I found a great……
June 28th, 2022 at 10:35 am
legitimate canadian mail order pharmacies https://anewearthmovement.org/community/profile/mefug/...
With thanks! I enjoy it!…
June 28th, 2022 at 8:13 pm
canadian prescriptions online http://sandbox.autoatlantic.com/community/profile/kawxvb/...
You said that adequately….
June 29th, 2022 at 10:44 am
cialis http://lwerfa.iwopop.com/...
Amazing many of helpful knowledge!…
June 29th, 2022 at 4:17 pm
cialis 5mg http://herbsd.iwopop.com/...
Incredible many of valuable knowledge….
June 30th, 2022 at 7:41 am
tadalafil tablets http://kawerf.iwopop.com/...
Point well applied.!…
June 30th, 2022 at 10:27 pm
Jae Storozuk…
I found a great……
July 1st, 2022 at 3:00 pm
авиатор игра наденьги…
blog topic…
July 3rd, 2022 at 11:12 am
cialis canada https://www.reddit.com/user/dotijezo/comments/9xlg6g/online_pharmacies/...
With thanks. An abundance of knowledge!
…