Why does the state monad fail?

Question

Intuitively, it seems to me that you can use traverse with the 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 does not implement the Traversable class. Why is this? I tried to figure out a way to implement the traverse for the state monad, and it seems that the difficulty is to extract the result of the state monad in order to transfer its function specified as the first argument of the traverse. It's impossible?

Answer 1

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

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

When t is State s , it becomes:

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

Obviously, we cannot write an implementation for all s , since we need to know how to create s or fa from nothing to continue. That would be a contradiction.

But it is possible to write an instance that satisfies the type for certain classes s . If we assume that s is 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 laws of Traversable . One of the laws:

 traverse Identity = Identity 

(recall that traverse f = sequence . fmap f )

This law is clearly not executed because the output action is mappend whereas the input action was not executed. 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 

This does not help, since now the output action ignores its input and is mempty , while the input action was not performed.

This does not mean that there are no types of s for which we were unable to create a legitimate instance of Traverse (State s) . For example, State () comes down to Identity , which is absolutely possible.

And if we can do State () , why not State Bool ? We can simply runState to perform the initial action on both True and False , save the result on the map, and then perform the resulting state action by searching on this map. This works for any finite enumerable state area. See this answer for more details.

Answer 2

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

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

As you can see, immediate a does not exist, this is the only result of the function.

Answer 3

Yes, this is really impossible. Consider the following definition of State :

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

In extract value of this data type would initially provide some state.

We can create a specialized extract function if we know the type of 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 cannot create a general extraction function. For example:

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

The above extract function is common. The only condition we can set is & bottom; which is wrong. This is safe if the function f :: s -> (a, s) transparently passes through its input signal (i.e. f = (,) a for some value of a ). However, f can take a certain state and use it to generate some value and a new state. Therefore, f can use its input opaque, and if the input is & bottom; then we get an error.

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

Now, for a data type to be an instance of Traversable , it must first be an instance of Foldable . Therefore, to make the State instance of Traversable , we must first 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 is of type Monoid m => (a -> m) -> State sa -> m . Therefore, the expression foldMap f (State g) should return a value of type Monoid m => m . Trivially, we can always return mempty by defining foldMap = const (const mempty) . However, in my humble opinion, this is not true because:

• In fact, we do not collapse anything, always return mempty .
• Each data type can be trivially created by a Foldable instance, always returning mempty .

The only way to create a value of type Monoid m => m is to apply f to some value x type a . However, we have no value of type a . If we could extract value of a from State sa , then we could apply f to this value, but we have already proved that it cannot determine the general extract function State sa , which will never work.

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

Answer 4

Such a function cannot exist.

You are requesting a function with this signature:

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

That is, if the function f :: a -> [a] specified and the state is calculated, trav returns a list. In particular, if I give you f and state calculation, you should tell me whether the list of results is null or not.

Now consider this f :

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

And try evaluating trav f (\s -> (s,s)) or even try to determine if this is an empty list.

You can write this function:

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

because the resulting list will always be the same length.