haskellfunctional-programmingmonadscategory-theorycomonad

Combining the state monad with the costate comonad


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.


Solution

  • 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:

    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.