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 [...]