Constructing minimal Haskell example on error-handling in the State Monad

Question

I'm twisting my brain into knots trying to understand how to combine the State monad with Maybe.

Let's start with a concrete (and intentionally trivial/unnecessary) example in which we use a State monad to find the sum of a list of numbers:

import Control.Monad.State

list :: [Int]
list = [1,4,5,6,7,0,3,2,1]

adder :: Int
adder = evalState addState list

addState :: State [Int] Int
addState = do
  ms <- get
  case ms of
    []     -> return 0
    (x:xs) -> put xs >> fmap (+x) addState

Cool.

Now let's modify it so that it returns a Nothing if the list contains the number 0. In other words, evalState addState' list should return Nothing (since list contains a 0). I thought it might look something like this...

addState' :: State [Int] (Maybe Int)
addState' = do
  ms <- get
  case ms of
    [] -> return (Just 0)
    (0:xs) -> return Nothing
    (x:xs) -> put xs >> fmap (fmap (+x)) addState'

...it works but I assume there's a better way to do this...

I've played around with StateT and MaybeT and I can't get them to work. I've looked at a couple of intros to Monad transformers but they either didn't touch on this particular combo (i.e., State + Maybe) or the examples were too complex for me to understand.

TL;DR: I'd appreciate if someone could show how to write this (admittedly trivial) piece of code using StateT and MaybeT (two examples). (I'm assuming it isn't possible to write this code without the use of transformers - is that incorrect?)

P.S. My understanding is that StateT is probably better suited for this example, but it would be helpful conceptually to see both examples, if not too much trouble.

Update: As pointed out by @Brenton Alker, my first version of the code above doesn't work because of simple typo (I was missing an apostrophe). In the interest of focusing the question on the use of StateT/MaybeT, I'm correcting the post above. Just wanted to include this note to give context to his post.

Answer 1

The type I would recommend using is:

StateT [Int] Maybe Int

A really simple way to use Maybe/MaybeT is to just call mzero whenever you want to fail and mplus whenever you want to recover from a failed computation. This works even if they are layered within other monad transformers.

Here's an example:

addState' :: StateT [Int] Maybe Int
addState' = do
  ms <- get
  case ms of
    []     -> return 0
    (0:xs) -> mzero
    (x:xs) -> put xs >> fmap (fmap (+x)) addState

-- This requires generalizing the type of `addState` to:
addState :: Monad m => StateT [Int] m Int

Notice that I wrote that in such a way that I didn't use any Maybe-specific operations. In fact, if you let the compiler infer the type signature it will deduce this more general type instead:

addState' :: MonadPlus m => StateT [Int] m Int

This works because StateT has the following MonadPlus instance:

instance MonadPlus m => MonadPlus (StateT s m) where ...

And Maybe will type-check as an instance of MonadPlus, which is why the above code works when we specialize m to Maybe.

Answer 2

I believe your solution is basically correct, you just have a few minor issues.

1. Your recursive call to addState is missing the prime - ie. it should be addState' (I suspect this is just an issue in pasting the question, given the reported error)
2. You're asserting adder :: Int, but in the new version it should be adder :: Maybe Int - I think this is the type error you're getting.

Unfortunately, I don't have the resources to try a transformers version at the moment.

Answer 3

This example implements a simple Stack using MaybeT (State [Int]) Int.

We have a State Monad that holds s -> (a, s) being s :: [Int] (a Stack) and a :: Maybe Int (Just the element you get out/put into the Stack or Nothing when you try to pop something out of an empty stack).

-- -----------------------------------------
-- -----------------------------------------
import Control.Monad.Trans.State
import Control.Monad.Trans.Maybe

-- -----------------------------------------
-- -----------------------------------------
pop2 :: MaybeT (State [Int]) Int
pop2 = MaybeT . state $ \xx -> case xx of
  [] -> (Nothing, [])
  x:xs -> (Just x, xs)

push2 :: Int -> MaybeT (State [Int]) Int
push2 x =  MaybeT . state $ \xs -> (Just x, x:xs)

-- -----------------------------------------
-- -----------------------------------------
dup2 = do
  x <- pop2
  push2 x
  push2 x

-- -----------------------------------------
-- -----------------------------------------
main = do
  print $ runState (runMaybeT dup2) [12, 34, 56]
  print $ runState (runMaybeT dup2) []

When we run the program, we get:

(Just 12,[12,12,34,56]) 
(Nothing,[])

Let's review the types:

Originally,

MaybeT :: m (Maybe a) -> MaybeT m a (m a monad enclosing a Maybe a)

We use m == State [Int] and a == Int

Therefore

MaybeT :: (State [Int]) (Maybe Int) -> MaybeT (State [Int]) Int

and

runMaybeT :: MaybeT m a -> m (Maybe a) == MaybeT (State [Int]) Int -> (State [Int]) (Maybe Int) (runMaybeT pulls out what MaybeT encloses).

and

runState of (State [Int]) (Maybe Int) == [Int] -> ((Maybe Int), [Int]) (runState pulls out what (State [Int]) (Maybe Int) encloses).