A Non-Unique Monad Instance

SourceMarkdownLaTeXPosted in Haskell, ProjectsComments


Just stopping in for a short post before continuing with a long-overdue series or two :) This post is a bit of a short fun one that describes a quest I had, and hopefully some useful extra ideas I found along the way.

Soon after I discovered Haskell, one question has plagued my mind. Day and night, I wondered…

Are there any Haskell types with more than one unique Monad instance?

This was a question that was pretty simple…so simple that I was sure many people had already asked and answered this. But I couldn’t really find any answers and nobody I asked at the time could really give me one either, so this soon embedded itself as a pretty deep mystery to my psyche.

The background?

Functor and Applicative

All Functor instances, if they exist, are unique for the type. The type uniquely determines the instance. There is only one possible Functor instance for [], one possible Functor instance for Maybe, Either, etc.

This fact is taken advantage of by GHC to allow you to derive, for some types, a Functor instance automatically.

ghci> :set -XDeriveFunctor
ghci> data Foo a = Bar [a] (Maybe (Foo a)) | Baz (Either String a) (Foo a)
ghci> let x = Bar [1, 3] (Just (Baz (Right 4) (Bar [10] Nothing)))
ghci> fmap (*2) x
Bar [2, 6] (Just (Baz (Right 8) (Bar [20] Nothing)))

There is no other possible Functor instance for that data type. Go ahead, try :D

data Foo a = Bar [a] (Maybe (Foo a)) | Baz (Either String a) (Foo a)

instance Functor Foo where
    fmap f (Bar xs y) = Bar (fmap f xs) (fmap f y)
    fmap f (Baz x fy) = Baz (fmap f x) (fmap f fy)

However, this is not the case for Applicative. Everyone knows of course about the normal (cartesian product) Applicative instance and the zippy Applicative instance for list:

instance Applicative [] where
    pure x    = [x]
    fs <*> xs = [ f x | f <- fs, x <- xs ]

instance Applicative [] where
    pure      = repeat
    fs <*> xs = zipWith ($) fs xs

What is also fairly established is that every noncommutative Applicative instance also has a “flipped” version:

-- a flipped IO Applicative
data FlipIO a = FlipIO { runFlipIO :: IO a }

instance Applicative FlipIO where
    pure x    = FlipIO (pure x)
    fi <*> xi = FlipIO $ do
                  x <- runFlipIO xi
                  f <- runFlipIO fi     -- note the backwards effects
                  return (f x)
data State s a = State { runState :: s -> (a, s) }

-- the normal instance
instance Applicative (State s) where
    pure x    = State $ \s0 -> (x, s0)
    fs <*> xs = State $ \s0 -> let (f, s1) = runState fs s0
                                   (x, s2) = runState xs s1
                               in  (f x, s2)

-- the flipped instance
instance Applicative (State s) where
    pure x    = State $ \s0 -> (x, s0)
    fs <*> xs = State $ \s0 -> let (x, s1) = runState xs s0
                                   (f, s2) = runState fs s1
                               in  (f x, s2)
ghci> liftA2 (,) getLine getLine
> hello         -- asking for the first field
> world         -- asking for the second field
("hello", "world")
ghci> runFlipIO $ liftA2 (,) (FlipIO getLine) (FlipIO getLine)
> hello         -- asking for the second field
> world         -- asking for the first field
("world", "hello")

Every non-commutative Applicative admits an alternative instance where “flipping” the order of the “effects” is also a valid Applicative instance. So, not Maybe or Either, but State, [], and IO.

-- free "flipped" Applicative instance
data Flipped f a = Flipped { runFlipped :: f a }

-- instance where (<*>) is the same, but the order of effects is switched
instance Applicative f => Applicative (Flipped f) where
    pure = Flipped . pure
    Flipped f <*> Flipped x = Flipped $ liftA2 (flip ($)) x f

Cool. Types that have Functor instances only have one. Types that have Applicative instances very often have more than one.

So, the obvious next question is…what about Monads? Is a Monad instance uniquely determined by its type?

Monad

The answer wasn’t that simple, for me. Yes, most Applicatives in the wild are non-unique, and there was a generating rule. But not so for Monads. You can’t have a Monad where the effects are switched, because for (>>=), you need the effects of the first action in order to even decide what the effects of the next action are.

I vaguely remember from my past two data types that are very similar yet have very different Monad and Applicative instances: (finite) lists, (infinite) streams. From the outset, the two have almost identical structure. A Stream is just a list with no []/nil:

data Stream a = a :~ Stream a

The Functor instance is identical:

instance Functor Stream where
    fmap f (x :~ xs) = f x :~ fmap f xs

And the (only??) Applicative instance is the ZipList instance for lists:

instance Applicative Stream where
    pure x = x :~ pure x
    (f :~ fs) <*> (x :~ xs) = f x :~ (fs <*> xs)

The Monad instance is however very different from that of lists:

instance Monad Stream where
    return x = x :~ return x
    xs >>= f = join' (fmap f xs)
      where
        join' :: Stream (Stream a) -> Stream a
        join' ((x :~ _) :~ yss) = x :~ join' (fmap tail' yss)
        tail' (_ :~ xs) = xs

The Monad instance itself is actually interesting enough to write about. It all revolves around join, where join takes a stream of streams and creates a stream of the diagonals. So it takes the first element of the first stream, the second element of the second stream, the third element of the third stream, etc.

This is actually a special case of the Monad instance for all fixed-sized ordered containers. A length 5 vector, for example, will have the same Applicative and Monad instance as described here: (<*>) with “zipping”, and join with grabbing the diagonal of the 5-vector of 5-vectors.

This was a promising lead, but, it doesn’t take too much thought to see that neither lists nor Stream are appropriate for both instances.

Aside

In case you were wondering, here is an elaboration :D

  • Fixed length vectors can’t have the normal list Applicative instance at all, unless they are of size 0 or 1. That’s because the result after (<*>), the resulting list’s length is the product of the original lists. So you can forget the Monad instance, too.

  • Streams give you no luck, either. The easiest way to see is by considering the analogous Monad instance, where join is the straight-up concatenation. m >>= return == m is clearly violated. If m is an infinite list, fmap return gives you an infinite list of infinite lists, “joining”/concatenating them back will just give you an infinite list of the first item in m.

    To put succincently, for Stream, concat == head.

  • Lists can have the Applicative instance fine, but not the Monad instance. Here we assume that zipping and “getting the diagonal” go only as “far as possible”, and stop when one of the lists is too short.

    This one is a little trickier, but the weakness is when you have lists of lists of lists of different lengths.

    ghci> let counterexample = [[[1]], [[], [2,3]]]
    ghci> join counterexample
    [[1], [2,3]]
    ghci> join. join $ counterexample
    [1,3]
    ghci> fmap join counterexample
    [[1], []]
    ghci> join . fmap join $ counterexample
    [1]

    For a monad, joining the inner layer and then joining it all should be the same as joining it all and joining it all. The order of the joining shouldn’t count. We can see this in the more haskelly monad laws by noting:

    ghci> id <=< (id <=< id) $ counterexample
    [1,2]
    ghci> (id <=< id) <=< id $ counterexample
    [1]

    So, dead end here.

So I didn’t really have any leads at that point; I tried a couple of other paths but nothing really panned out. So I shelved it for a while.

Revelation

Several centuries later1, the final revelation came as many revelations do in Haskell — from a hint by Edward Kmett. He pointed out something interesting regarding a Monad instance that I had yet to notice:

instance Monoid w => Monad ((,) w) where

This is the classic “Writer” monad instance, which is literally about as old as monads in functional programming is.

The key is that the Monad instance of (w,) depends on the Monoid instance of w. This is the “log”, so to speak. You need a Monoid instance in order to make the Monad instance…and the behavior of the Monad instance is directly determined by the behavior of the Monoid instance of w.

And…Monoid instances in Haskell are rarely ever unique! A different Monoid instance would create a very different Monad instance for the same type!

So, by factoring out the dependency on an external Monoid instance, you get…

data Two a = One a | Two a

instance Functor Two where
    fmap f (One a) = One (f a)
    fmap f (Two a) = Two (f a)

and…voila! There it is!

This type is basically equivalent to (Bool, a). And Bool has multiple Monoids on it. Instead of requiring an outside Monoid instance, we can encode the instance directly into the behavior of (>>=). And here we go!

Our instances are basically the Writer instance for (Bool, a), with different Monoid instances for Bool.

The first instance:

instance Applicative Two where
    pure = One
    One f <*> One x = One (f x)
    One f <*> Two x = Two (f x)
    Two f <*> One x = Two (f x)
    Two f <*> Two x = Two (f x)

instance Monad Two where
    return = One
    One x >>= f = f x
    Two x >>= f = case f x of
                    One y -> Two y
                    Two y -> Two y

Which represents the monoids formed by (&&) with True or by (||) with False (depending on which one you pick as True and which one you pick as False; the two instances are isomorphic)

The second:

instance Applicative Two where
    pure = One
    One f <*> One x = One (f x)
    One f <*> Two x = Two (f x)
    Two f <*> One x = Two (f x)
    Two f <*> Two x = One (f x)

instance Monad Two where
    return = One
    One x >>= f = f x
    Two x >>= f = case f x of
                    One y -> Two y
                    Two y -> One y

Which represents the monoid formed by (/=) (or “XOR”) with False.

And there you go. One type, two possible unique, non-isomorphic Monad instances.

Aside

One interesting thing to note is that the Monad instance for (->) a requires no monoid constraint, and the Monad instance for (,) a does.

Interestingly enough, if we look at comonads, the Comonad instance for (->) a does require a monoid constraint on a (so for example there are many unique Comonad instances for things isomorphic to (->) a where a has more than one Monoid instance) and and the Comonad instance for (,) a does not require a monoid constraint on a.

Is there some duality at play here?

The answer is, apparently, yes! But according to Edward Kmett, it is one that is pretty hard to arrive at and a big headache and overall not worth the time to dig into. So you’re going to have to take my second-hand word for it.


  1. More accurately, “about a year”

Comments powered by Disqus