Sat 6 Jan 2018

Is `State`

a `Comonad`

?

Not `Costate`

or rather, `Store`

as we tend to call it today, but actually `State s`

itself?

Let's see!

Recently there was a post to reddit in which the author `King_of_the_Homeless`

suggested that he might have a `Monad`

for `Store`

. Moreover, it is one that is compatible with the existing `Applicative`

and `ComonadApply`

instances. My knee-jerk reaction was to disbelieve the result, but I'm glad I stuck with playing with it over the last day or so.

In a much older post, I showed how to use the `Co`

comonad-to-monad-transformer to convert `Store s`

into `State s`

, but this is a different beast, it is a monad directly on `Store s`

.

{-# language DeriveFunctor #-} import Control.Comonad import Data.Semigroup data Store s a = Store { peek :: s -> a, pos :: s } deriving Functor instance Comonad (Store s) where extract (Store f s) = f s duplicate (Store f s) = Store (Store f) s instance (Semigroup s, Monoid s) => Applicative (Store s) where pure a = Store (const a) mempty Store f s < *> Store g t = Store (\m -> f m (g m)) (mappend s t) instance Semigroup s => ComonadApply (Store s) where Store f s < @> Store g t = Store (\m -> f m (g m)) (s <> t) instance (Semigroup s, Monoid s) => Monad (Store s) where return = pure m >>= k = Store (\s -> peek (k (peek m s)) s) (pos m `mappend` pos (k (peek m mempty)))

My apologies for the `Semigroup`

vs. `Monoid`

, noise, as I'm still using GHC 8.2 locally. This will get a bit cleaner in a couple of months.

Also, `peek`

here is flipped relative to the version in `Control.Comonad.Store.Class`

so that I can use it directly as a field accessor.

As I noted, at first I was hesitant to believe it could work, but then I realized I'd already implemented something like this for a special case of Store, in the 'streams' library, which got me curious. Upon reflection, this feels like the usual Store comonad is using the ability to distribute `(->) e`

out or `(,) e`

in using a "comonoid", which is always present in Haskell, just like how the State monad does. But the type above seems to indicate we can go the opposite direction with a monoid.

So, in the interest of exploring duality, let's see if we can build a comonad instance for `State s`!

Writing down the definition for state:

newtype State s a = State { runState :: s -> (a, s) } deriving Functor instance Applicative (State s) where pure a = State $ \s -> (a, s) State mf < *> State ma = State $ \s -> case mf s of (f, s') -> case ma s' of (a, s'') -> (f a, s'') instance Monad (State s) where return = pure State m >>= k = State $ \s -> case m s of (a, s') -> runState (k a) s'

Given a monoid for out state, extraction is pretty obvious:

instance Monoid s => Comonad (State s) where extract m = fst $ runState m mempty

But the first stab we might take at how to duplicate, doesn't work.

duplicate m = State $ \s -> (State $ \t -> runState m (mappend s t) , s )

It passes the `extract . duplicate = id` law easily:

extract (duplicate m) = extract $ State $ \s -> (State $ \t -> runState m (mappend s t), s) = State $ \t -> runState m (mappend s mempty) = State $ \t -> runState m t = State $ runState m = m

But fails the second law:

fmap extract (duplicate m) = fmap extract $ State $ \s -> (State $ \t -> runState m (mappend s t), s) = State $ \s -> (extract $ State $ \t -> runState m (mappend s t), s) = State $ \s -> (fst $ runState m (mappend s mempty), s) = State $ \s -> (evalState m s, s)

because it discards the changes in the state.

But the `King_of_the_Homeless`

's trick from that post (and the Store code above) can be modified to this case. All we need to do is ensure that we modify the output state 's' as if we'd performed the action unmolested by the inner monoidal state that we can't see.

duplicate m = State $ \s -> ( State $ \t -> runState m (mappend s t) , snd $ runState m s )

Now:

extract (duplicate m) = extract $ State $ \s -> (State $ \t -> runState m (mappend s t), snd $ runState m s) = State $ \t -> runState m (mappend mempty t) = State $ \t -> runState m t = State $ runState m = m

just like before, but the inner extraction case now works out and performs the state modification as expected:

fmap extract (duplicate m) = fmap extract $ State $ \s -> (State $ \t -> runState m (mappend s t), snd $ runState m s) = State $ \s -> (extract $ State $ \t -> runState m (mappend s t), snd $ runState m s) = State $ \s -> (fst $ runState m (mappend s mempty), snd $ runState m s) = State $ \s -> (fst $ runState m s, snd $ runState m s) = State $ \s -> runState m s = State $ runState m = m

This is still kind of a weird beast as it performs the state action twice with different states, but it does pass at least the left and right unit laws.

Some questions:

1. Proving associativity is left as an exercise. It passes visual inspection and my gut feeling, but I haven't bothered to do all the plumbing to check it out. I've been wrong enough before, it'd be nice to check!

[Edit: Simon Marechal (bartavelle) has a coq proof of the associativity and other axioms.]

2. Does this pass the `ComonadApply`

laws?

instance Monoid s => ComonadApply (State s) where (< @>) = (< *>)

[Edit: No.]

3. The streams code above suggests at least one kind of use-case, something like merging together changes of position in a stream, analogous to the "zipping monad" you have on infinite streams. But now the positions aren't just Integers, they are arbitrary values taken from any monoid you want. What other kind of spaces might we want to "zip" in this manner?

4. Is there an analogous construction possible for an "update monad" or "coupdate comonad"? Does it require a monoid that acts on a monoid rather than arbitrary state like the semi-direct product of monoids or a "twisted functor"? Is the result if it exists a twisted functor?

5. Does `Co` translate from this comonad to the monad on `Store`?

6. Is there a (co)monad transformer version of these?

Link: Gist

January 13th, 2018 at 4:31 pm

Is it essential that s is used twice in the definition of bind:

(\s -> peek (k (peek m s)) s)

m s produces another monoidal value so, in principle, it could be used instead (either alone or mappended to s). Would that violate the laws?

July 1st, 2018 at 6:38 am

[...] Is State a Comonad? ~ Edward Kmett (@kmett) #Haskell [...]

September 23rd, 2022 at 4:41 am

stromectol medication https://500px.com/p/skulogovid/?view=groups...Good knowledge. Thanks a lot!…

September 23rd, 2022 at 8:44 am

canadian pharmacy https://500px.com/p/bersavahi/?view=groups...Many thanks! Wonderful information….

September 24th, 2022 at 1:50 am

canada online pharmacies https://reallygoodemails.com/canadianpharmaceuticalsonlineusa...Fantastic facts, Thank you!…

September 24th, 2022 at 5:26 am

Online viagra https://www.provenexpert.com/canadian-pharmaceuticals-online-usa/...You said it adequately.!…

September 24th, 2022 at 10:33 am

canada pharmacy online https://sanangelolive.com/members/pharmaceuticals...This is nicely expressed. ….

September 26th, 2022 at 9:31 am

Tadalafil https://melaninterest.com/user/canadian-pharmaceuticals-online/?view=likes...Many thanks! I appreciate this….

September 26th, 2022 at 1:33 pm

Buy viagra online https://haikudeck.com/canadian-pharmaceuticals-online-personal-presentation-827506e003...You revealed it perfectly….

September 26th, 2022 at 5:41 pm

Viagra cost https://buyersguide.americanbar.org/profile/420642/0...Excellent tips. Cheers!…

September 27th, 2022 at 1:22 am

canadian online pharmacy https://experiment.com/users/canadianpharmacy...Effectively voiced truly. ….

September 27th, 2022 at 11:00 am

stromectol tablets https://challonge.com/esapenti...Beneficial postings. Thanks a lot….

September 27th, 2022 at 3:27 pm

Viagra for daily use https://challonge.com/gotsembpertvil...Cheers! Numerous facts!

…

September 28th, 2022 at 5:11 am

Tadalafil https://challonge.com/citlitigolf...You suggested that effectively!…

September 28th, 2022 at 8:44 am

stromectol scabies https://order-stromectol-over-the-counter.estranky.cz/clanky/order-stromectol-over-the-counter.html...Beneficial write ups. Thanks a lot….

September 28th, 2022 at 3:11 pm

Viagra reviews https://soncheebarxu.estranky.cz/clanky/stromectol-for-head-lice.html...Amazing lots of wonderful tips….

September 29th, 2022 at 2:56 pm

Viagra from canada https://inflavnena.zombeek.cz/...Point certainly regarded…..

September 30th, 2022 at 4:40 am

wwwi.odnoklassniki-film.ru…wwwi.odnoklassniki-film.ru…

September 30th, 2022 at 7:04 am

site…site…

September 30th, 2022 at 9:12 am

canada pharmacies https://www.myscrsdirectory.com/profile/421708/0...Regards, I like it….

September 30th, 2022 at 4:24 pm

Interactions for viagra https://supplier.ihrsa.org/profile/421717/0...Nicely put. Kudos!…

October 1st, 2022 at 6:45 am

Viagra vs viagra vs levitra https://wefbuyersguide.wef.org/profile/421914/0...You said it nicely.!…

October 1st, 2022 at 10:46 am

Viagra for sale https://legalmarketplace.alanet.org/profile/421920/0...Fantastic facts. Kudos….

October 2nd, 2022 at 4:23 am

Viagra cost https://moaamein.nacda.com/profile/422018/0...You have made the point!…

October 2nd, 2022 at 8:49 am

Viagra pills https://www.audiologysolutionsnetwork.org/profile/422019/0...Nicely put, Thank you!…

October 2nd, 2022 at 12:06 pm

buy viagra usa https://network.myscrs.org/profile/422020/0...Nicely put. With thanks!…

October 3rd, 2022 at 5:51 am

Viagra cost https://sanangelolive.com/members/canadianpharmaceuticalsonlineusa...Amazing posts. Thank you….

October 3rd, 2022 at 9:17 am

Viagra rezeptfrei https://sanangelolive.com/members/girsagerea...Amazing content. With thanks!…

October 4th, 2022 at 8:04 am

buy viagra online usa https://www.ecosia.org/search?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Whoa lots of wonderful knowledge….

October 4th, 2022 at 12:02 pm

Low cost viagra 20mg https://www.mojomarketplace.com/user/Canadianpharmaceuticalsonline-EkugcJDMYH...Good tips. Thank you….

October 4th, 2022 at 4:13 pm

canadian online pharmacy https://seedandspark.com/user/canadian-pharmaceuticals-online...Superb content, Thanks a lot….

October 5th, 2022 at 9:15 am

Viagra purchasing https://www.giantbomb.com/profile/canadapharmacy/blog/canadian-pharmaceuticals-online/265652/...Many thanks, Numerous information!

…

October 5th, 2022 at 5:52 pm

Online viagra https://search.gmx.com/web/result?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Position well applied…..

October 5th, 2022 at 7:52 pm

rftrip.ru…rftrip.ru…

October 6th, 2022 at 2:58 am

Tadalafil https://search.seznam.cz/?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…You said that terrifically!…

October 6th, 2022 at 6:39 am

Tadalafil 5mg https://sanangelolive.com/members/unsafiri...Nicely spoken indeed. ….

October 6th, 2022 at 10:56 am

Viagra great britain …Fantastic posts. With thanks!…

October 6th, 2022 at 4:53 pm

canadian pharcharmy online https://swisscows.com/en/web?query=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Useful content. Thanks….

October 7th, 2022 at 4:15 am

Viagra generico online https://www.dogpile.com/serp?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Thank you. A good amount of tips!

…

October 7th, 2022 at 11:25 am

Viagra vs viagra …Beneficial knowledge. Cheers!…

October 8th, 2022 at 7:22 am

canadian online pharmacies https://search.givewater.com/serp?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Great content, With thanks….

October 9th, 2022 at 6:00 am

Viagra 20 mg …Thanks a lot. A good amount of info!

…

October 9th, 2022 at 11:07 am

Viagra 5 mg https://results.excite.com/serp?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Effectively spoken without a doubt. ….

October 9th, 2022 at 3:36 pm

canadian pharmacy cialis https://www.infospace.com/serp?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Thanks! Numerous data!

…

October 10th, 2022 at 1:07 am

dolpsy.ru…dolpsy.ru…

October 10th, 2022 at 7:53 am

Viagra uk https://headwayapp.co/canadianppharmacy-changelog...Nicely expressed indeed! ….

October 11th, 2022 at 11:16 am

Viagra cost https://canadianpharmaceuticalsonline.as.me/schedule.php...Thanks, Ample information.

…

October 13th, 2022 at 1:10 pm

canadian pharmaceuticals online https://feeds.feedburner.com/bing/stromectolnoprescription...Thanks a lot, Loads of information!

…

October 14th, 2022 at 5:36 am

Viagra uk https://reallygoodemails.com/orderstromectoloverthecounterusa...With thanks! Fantastic information….