Why is this Applicative instance for StateT working?

user_11728033 0
Viewed 137

I am a Haskell (and CS) beginner. I am working my way through the haskellbook. I was implementing the Applicative instance for StateT where StateT is defined as :

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

It is mentioned in the book that for creating an Applicative instance for StateT s m we need a Monad constraint on m rather than an Applicative constraint as one would expect. I had also reached the same conclusion on reading the accepted answer for the SO answer referenced in the book. But, I tried to create an Applicative instance with an Applicative constraint on m for better understanding, and it successfully compiled. I also tried it on a few examples and it seems to work fine. Can someone please explain, what's wrong here?

instance (Applicative m) => Applicative (StateT s m) where
  pure a = StateT $ \s -> pure $ (a, s)
  (<*>) :: (StateT s m (a -> b)) -> (StateT s m a) -> (StateT s m b)
  (StateT smf) <*> (StateT sma) = StateT $ \s -> (f) <$> (smf s) <*> (sma s)
                                  where
                                    f :: (a -> b, s) -> (a, s) -> (b, s)
                                    f (ff, s) = \(a, s) -> (ff a,s)


*StateT> s1 = StateT (\s -> return (4, s))
*StateT> s2 = map (+) s1
*StateT> s3 = StateT (\s -> return (20, s))
*StateT> runState (s2 <*> s3) * 10
(24,10)
*StateT>

EDIT : As @Koterpillar advised me to try this with examples where state is also modified. I tried with this example. Also, here is the Monad constraint version, which I think also doesn't behave as it should. I think the problem is with states not being linked together somehow. If someone can shed some light on this topic, I would be grateful.

applicative state monads functional-programming haskell
1 Answers

This is what <*> for StateT should do:

  1. Run smf with the initial state
  2. Run sma with the state from smf
  3. Return this final state

This is what your code does:

  1. Run smf with the initial state
  2. Run sma with the initial state
  3. Return this final state

In other words, the bug is that the state changes caused by smf are discarded.

We can demonstrate this issue with code that modifies the state in smf. For example:

s1 = StateT $ \s -> return (const (), s + 1)
s2 = StateT $ \s -> return ((), s)

Then runState (s1 <*> s2) 0 will return ((), 1) with the standard implementation, but ((), 0) with your one.

user_6171590
Related