Stacking ExceptT and StateT in Haskell

In the process of learning about effects in racket, I came across an interesting question I could reason about using types in Haskell: What is the difference between stacking StateT on ExceptT versus ExceptT on StateT?

StateT over ExceptT

If in doubt, keep the documentation of ExceptT and StateT ready.

type SE = StateT Int (ExceptT String Identity) Char

test :: SE

a = runStateT test 0 :: ExceptT String Identity (Char, Int)
b = runExceptT a :: Either String (Char, Int)

The happy case

test = do
    put 10
    return 'A'

a = ExceptT (Identity (Right ('A',10)))
b = Identity (Right ('A', 10))

runStateT :: StateT Int (ExceptT String Identity) Char -> Int -> ExceptT String Identity (Char, Int) takes an Int and runs a computation SE to give a state and a result, wrapped in an ExceptT. In this case, the computation is a success.

Let's try throwing an error

test = do
    put 10
    throwError "No"

a = ExceptT (Identity (Left "No"))
b = Identity (Left "No")

Why is the state not included when there's an error? The type of b indicates the error (the Left side of Either) does not carry state. This is interesting... Where is this behavior defined? Let's look at the documentation.

Given a StateT s m a, its constructor is StateT (s -> m (a, s)) and the constructor of ExceptT e m a is ExceptT (m (Either e a)). In our case, the constructor becomes StateT (Int -> ExceptT String Identity (Char, Int)). Here, s is the state, m is the inner monad and a is the type of result.

So, that explains why we don't see the state tied to an error. Furthermore, any modifications to the state after the error are not tracked.

ExceptT over StateT

Consider the dual of SE

type ES = ExceptT String (StateT Int Identity) Char
a = runExceptT test' :: StateT Int Identity (Either String Char)
b = runState a 0 :: (Either String Char, Int)

The happy case

test' = do
    put 10
    return 'A'

This works as expected and we get a b = (Right 'A', 10). We can not inspect a because it is a computation that depends on a future state.

What if we throw an error?

test' = do
    put 10
    throwError "No"

b becomes (Left "No", 10). So, it does preserve the state after all! As the type signature of b implies, we always have the state returned no matter whether the computation ended up in a Left or a Right.

Control

The Alternative does not undo state changes and ends up with b = (Right 'X',10).

go :: ES
go = do
    put 42
    let x = (test' <|>)
    test' <|> return 'X'

test' :: ES
test' = do
    put 10
    throwError "No"

On the other hand, when the StateT monad is the outer layer, the computation can indeed back out on error and restore the old state. So, b becomes Identity (Right ('X',42)). Isn't this cool!?

go :: SE
go = do
    put 42
    test <|> return 'X'

test :: SE
test = do
    put 10
    throwError "No"

Note: You can extract the value from Identity monad using runIdentity :: Identity a -> a.

The excellent explanation on this stackoverflow post inspires this post.