Unable to understand how State Monad get it's state in this code

Question

I kind of understand State Monad's usefulness it propagating new values in a sequential execution. But in the following code, I'm having trouble in understanding how and where addResult get it's updated state everytime it gets evaluated.

fizzBuzz :: Integer -> String
fizzBuzz n
   | n `mod` 15 == 0 = "FizzBuzz"
   | n `mod` 5 == 0 = "Buzz"
   | n `mod` 3 == 0 = "Fizz"
   | otherwise = show n

fizzbuzzList :: [Integer] -> [String]
fizzbuzzList list = execState (mapM_ addResult list) []

addResult :: Integer -> State [String] ()
addResult n = do
    xs <- get
    let result = fizzBuzz n
    put (result : xs)

main :: IO ()
main = mapM_ putStrLn $ fizzbuzzList [1..100]

This code evaluates to produce

1, 2, Fizz...

I just couldn't figure out how the new value produced by addResult gets appended to the previously produced list. Can you please help me understand how mapM_ addResult list does it's stuff here?

Answer 1

As you have correctly observed, the State monad is used to thread some external 'state' value through a series of computations. However, you ask how this state is 'persisted' across multiple invocations of your function addResult :: Integer -> State [String] () on each value of the list list. The trick is the definition of mapM_. We'll start by considering the simpler function mapM:

mapM f [] = return []
mapM f (x:xs) = do
    fx <- f x
    fxs <- mapM f xs
    return (fx : fxs)

If we mentally 'expand' this recursive definition out with, say, an example list [x1,x2,x3,x4,...,xn], we'll observe that the value of mapM f [x1,...,xn] would be another monadic computation:

do
    fx1 <- f x1
    fx2 <- f x2
    -- etc.
    fxn <- f xn
    return [fx1,fx2,...,fxn]

So mapM basically 'sticks together' a bunch of monadic computations into one big one, by running them together in order. Which explains how you build up a list instead of producing many smaller ones: the get at the beginning of addResult gets the state from the last run, not from the beginning, because you're running all the computations together, like so:

do
    fl0 <- addResult (list !! 0)
    fl1 <- addResult (list !! 1)
    -- etc. like before

(If you read carefully, you'll notice I've been talking about mapM, but you actually used mapM_. They're exactly the same, except that the latter returns ().)