Why isn't the state monad traversable?

Intuitively, it seems to me that one could use traverse with a state monad, for example:

traverse (\a -> [a, a+1]) (state (\s -> (1, s + 1))) 
  = [state (\s -> (1, s + 1), state (\s -> (2, s + 1)]

But the state monad doesn't implement the Traversable typeclass. Why is that? I've tried to figure out a way to implement traverse for the state monad, and it seems that the difficulty is to extract the result of the state monad in order to pass it to the function given as first argument of traverse. Is it impossible?

Solution

To implement Traversable t, you need to implement a function of this type:

sequenceA :: forall f a. Applicative f => t (f a) -> f (t a)

When t is State s, this becomes:

sequenceA :: forall f a. Applicative f => State s (f a) -> f (State s a)

Obviously we can't write an implementation for all s, since we'd have to know either how to create an s or an f a out of nothing in order to proceed. That would be a contradiction.

But it's possible to write an instance that satisfies the type for certain classes of s. If we assume that s is a Monoid, we could do this:

instance (Monoid m) => Traversable (State m) where
  sequenceA (State run) = fmap (\a -> State (\s' -> (mappend s s', a)) fa 
    where (s, fa) = run mempty

But this does not satisfy the Traversable laws. One of the laws is:

traverse Identity = Identity

(recall that traverse f = sequence . fmap f)

This law clearly doesn't hold because the output action mappends whereas the input action did not. OK, how about we just don't mappend:

instance (Monoid m) => Traversable (State m) where
  sequenceA (State run) = fmap (\a -> State (\_ -> (s, a)) fa 
    where (s, fa) = run mempty

That doesn't help, since now the output action ignores its input and subsitutes mempty whereas the input action did not.

This doesn't mean that there aren't types s for which we couldn't construct a lawful Traverse (State s) instance. For example, State () reduces to Identity, which absolutely is traversable.

And if we can do State (), why not State Bool? We can just runState the original action at both True and False, store the result in a map, and then have the resulting state action perform a lookup in that map. This works for any finitely enumerable state domain. See this answer for details.