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?
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 mappend
s 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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With