2

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.

specdrake
  • 84
  • 1
  • 8

1 Answers1

3

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.

Lambda Fairy
  • 13,814
  • 7
  • 42
  • 68
  • Ah, I think I understand now. That's the mistake I am doing in the `Monad` constraint version too. I have to feed initial state `s` to `smf` and then the state returned from `smf` to `sma`. I thought of combining the two states but they are not `Semigroup`. – specdrake Jun 29 '20 at 12:33
  • This kind of threading of states reminds of `bind` somehow. Maybe that's why we need a Monad. – specdrake Jun 29 '20 at 12:35
  • 1
    If you `<>` the states instead, then you get a `Writer` monad -- and indeed that has a `Monoid` constraint. (It needs `Monoid`, not just `Semigroup`, to provide an empty state for `return`.) – Lambda Fairy Jun 29 '20 at 12:39
  • Oh, I don't know about `Writer` monads yet, but thanks a lot. – specdrake Jun 29 '20 at 12:40