Why isn't the state monad traversable?

Question

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?

Answer 1

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.

Answer 2

Being Traversable requires being Foldable; but State monad is not - you cannot foldMap it, because its value is simple not here.

type State s = StateT s Indentity
newtype StateT s m a = State { runState :: s -> m (s, a) }

As you can see, there is no immediate a to fold over here, its only result of the function.

Answer 3

Yes, it is indeed impossible. Consider the following definition of State:

newtype State s a = State { runState :: s -> (a, s) }

To extract the value this data type we would first need to supply some state.

We can create a specialized extract function if we know the type of the state. For example:

extract' :: State () a -> a
extract' (State f) = f ()

extractT :: State Bool a -> a
extractT (State f) = f True

extractF :: State Bool a -> a
extractF (State f) = f False

However, we can't create a generic extract function. For example:

extract :: State s a -> a
extract (State f) = f undefined

The above extract function is generic. The only state we can supply is ⊥ which is incorrect. It is only safe if the function f :: s -> (a, s) passes along its input transparently (i.e. f = (,) a for some value a). However, f may take some state and use it to generate some value and a new state. Hence, f may use its input non-transparently and if the input is ⊥ then we get an error.

Thus, we cannot create a generic extract function for the State data type.

Now, for a data type to be an instance of Traversable it first needs to be an instance of Foldable. Hence, to make State an instance of Traversable we first need to define the following instance:

instance Foldable (State s) where
    foldMap f (State g) = mempty
    -- or
    foldMap f (State g) = let x = f (extract g) in mconcat [x]
    -- or
    foldMap f (State g) = let x = f (extract g) in mconcat [x,x]
    -- or
    foldMap f (State g) = let x = f (extract g) in mconcat [x,x,x]
    -- ad infinitum

Note that foldMap has the type Monoid m => (a -> m) -> State s a -> m. Hence, the expression foldMap f (State g) must return a value of the type Monoid m => m. Trivially, we can always return mempty by defining foldMap = const (const mempty). However, in my humble opinion this is incorrect because:

1. We aren't really folding anything by always returning mempty.
2. Every data type can be trivially made an instance of Foldable by always returning mempty.

The only other way to produce a value of the type Monoid m => m is to apply f to some value x of the type a. However, we don't have any value of the type a. If we could extract the value a from State s a then we could apply f to that value, but we already proved that it's not possibly to define a generic extract function for State s a that never crashes.

Thus, State s cannot be made an instance of Foldable and consequently it cannot be an instance of Traversable.

Answer 4

Such a function can't exist.

You are asking for a function with this signature:

trav :: (a -> [a]) -> (s -> (a,s)) -> [ s -> (a,s) ]

That is, given a function f :: a -> [a] and a state computation, trav returns a list. In particular, if I give you f and a state computation, you should be able tell me if the result list is null or not.

Now consider this f:

f :: Int -> [Int]
f 0 = []
f a = [a]

And try to evaluate trav f (\s -> (s,s)) or even try to determine if it is the empty list.

You can write this function:

trav' :: [ a -> a ] -> (s -> (a,s)) -> [ s -> (a,s) ]

because the resulting list will always have the same length.