Combining the state monad with the costate comonad

Question

How to combine the state monad S -> (A, S) with the costate comonad (E->A, E)?

I tried with both obvious combinations S -> ((E->A, E), S) and (E->S->(A, S), E) but then in either case I do not know how to define the operations (return, extract, ... and so on) for the combination.

Answer 1

Combining two monads O and I yields a monad if either O or I is copointed, i.e. have an extract method. Each comonad is copointed. If both O and I` are copointed, then you have two different "natural" ways to obtain a monad which are presumably not equivalent.

You have:

unit_O :: a -> O a
join_O :: O (O a) -> O a
unit_I :: a -> I a
join_I :: I (I a) -> I a

Here I've added _O and _I suffixed for clarity; in actual Haskell code, they would not be there, since the type checker figures this out on its own.

Your goal is to show that O (I O (I a))) is a monad. Let's assume that O is copointed, i.e. that there is a function extract_O :: O a -> a.

Then we have:

unit :: a -> O (I a)
unit = unit_O . unit_I
join :: O (I (O (I a))) -> O (I a)

The problem, of course, is in implementing join. We follow this strategy:

• fmap over the outer O
• use extract_O to get ride of the inner O
• use join_I to combine the two I monads

This leads us to

join = fmap_O $ join_I . fmap_I extract

To make this work, you'll also need to define

newtype MCompose O I a = MCompose O (I a)

and add the respective type constructors and deconstructors into the definitions above.

The other alternative uses extract_I instead of extract_O. This version is even simpler:

join = join_O . fmap_O extract_I

This defines a new monad. I assume you can define a new comonad in the same way, but I haven't attempted this.

Answer 2

As the other answer demonstrates, both of the combinations S -> ((E->A, E), S) and (E->S->(A, S), E) have Monad and Comonad instances simultaneously. In fact giving a Monad/Comonad instance is equivalent to giving a monoid structure to resp. its points ∀r.r->f(r) or its copoints ∀r.f(r)->r, at least in classical, non-constructive sense (I don't know the constructive answer). This fact suggests that actually a Functor f has a very good chance that it can be both Monad and Comonad, provided its points and copoints are non-trivial.

The real question, however, is whether the Monad/Comonad instances constructed as such do have natural computational/categorical meanings. In this particular case I would say "no", because you don't seem to have a priori knowledge about how to compose them in a way that suit your computational needs.

The standard categorical way to compose two (co)monads is via adjunctions. Let me summarize your situation:

      Fₑ         Fₛ
      -->       -->
Hask  ⊣   Hask  ⊣ Hask
      <--       <--
      Gₑ         Gₛ

Fₜ(a) = (a,t)
Gₜ(a) = (t->a)

Proof of Fₜ ⊣ Gₜ:

Fₜ(x) -> y   ≃
(x,t) -> y   ≃
x  -> (t->y) ≃
x  -> Gₜ(y)

Now you can see that the state monad (s->(a,s)) ≃ (s->a,s->s) is the composition GₛFₛ and the costate comonad is FₑGₑ. This adjunction says that Hask can be interpreted as a model of the (co)state (co)algebras.

Now, 'adjunctions compose.' For example,

FₛFₑ(x) -> y ≃
Fₑ(x)   -> Gₛ(y) ≃
x       -> GₑGₛ(y)

So FₛFₑ ⊣ GₑGₛ. This gives a pair of a monad and a comonad, namely

T(a) = GₑGₛFₛFₑ(a)
     = GₑGₛFₛ(a,e)
     = GₑGₛ(a,e,s)
     = Gₑ(s->(a,e,s))
     = e->s->(a,e,s)
     = ((e,s)->a, (e,s)->(e,s))

G(a) = FₛFₑGₑGₛ(a)
     = FₛFₑGₑ(s->a)
     = FₛFₑ(e->s->a)
     = Fₛ(e->s->a,e)
     = (e->s->a,e,s)
     = ((e,s)->a, (e,s))

T is simply the state monad with the state (e,s), G is the costate comonad with the costate (e,s), so these do have very natural meanings.

Composing adjunctions is a natural, frequent mathematical operation. For example, a geometric morphism between topoi (kind of Cartesian Closed Categories which admit complex (non-free) constructions at the 'type level') is defined as a pair of adjunctions, only requiring its left adjoint to be left exact (i.e. preserves finite limits). If those topoi are sheaves on topological spaces, composing the adjunctions simply corresponds to composing (unique) continuous base change maps (in the opposite direction), having a very natural meaning.

On the other hand, composing monads/comonads directly seems to be a very rare practice in Mathematics. This is because often a (co)monad is thought of as a carrier of an (co)algebraic theory, rather than as a model. In this interpretation the corresponding adjunctions are the models, not the monad. The problem is that composing two theories requires another theory, a theory about how to compose them. For example, imagine composing two theories of monoids. Then you may get at least two new theories, namely the theory of lists of lists, or ring-like algebras where two kinds of binary operations distribute. Neither is a priori better/more natural than the other. This is the meaning of "monads don't compose"; it doesn't say the composition cannot be a monad, but it does say you will need another theory how to compose them.

In contrast, composing adjunctions naturally results in another adjunction simply because by doing so you are implicity specifying the rules of composing two given theories. So by taking the monad of the composed adjunction you get the theory that also specifies the rules of composition.