This is not a monad tutorial. These are my notes and code to help me grok monads. 🙂
As part of learning Haskell there is for some, perhaps many – including me, the ascent of Mount Monad!
I’m finding the way to ‘get it’ is to keep chipping away at Monads, read, absorb, write some code then rinse and repeat! This creates a familiarity with the symbols, with the do, >>= and >> being different faces of the same coin.
As part of this launderette of code I started writing simple Haskell functions and then pulled them apart and rewrote them using the State Monad. Just as a learning exercise.

Let’s start with a very simple function to sum a list of integers.

Looking at this from a stateful perspective, to determine what changes, we see the function is called repeatedly with a list of decreasing length whilst the accumulated sum increases.
This suggests that the State can be modelled using a tuple of Int and a list of Int. i.e. giving the signature

For the moment the implementation is undefined and we can write the following function that will compile.

The function takes a list of Int and returns an Int and internally it evaluates the state from the initial state that has an accumulated sum of 0 and an initial list that is the supplied list of Int.
So, what must the implementation of sumListS look like? Well, we need to get the current state and update the running total, then, if we’ve finished just call the return function with the updated total as the argument, otherwise update the state and put it back and continue. First let’s write it using do notation.

Line 4 gets the current state.
Line 5 checks the termination condition and calls the return function with the updated sum.
Otherwise we execute line 9 and then line 10.
Line 9 puts an updated state – which is an increased total and a reduced list.
Line 10 recurses.

Notice that with lines 8,9 and 10 we are actually sequencing two actions so can write it as

i.e. the result of put is ignored in the invoked lambda expression \_ -> sumList and because it’s ignored we can write it more succinctly as

Also the line (sm, (x:xs)) <- get can be written as get >>= \(sm, (x:xs)) -> ….
So, using bind notation the completed function is

How about the factorial function?
Here’s a simple implementation

And in State Monad style this becomes

Notice the use of fmap to lift the function (*x) into the monad. I won’t add any more but it is instructive to just try it as an exercise.

Now, to get to the title of this post! How can we write the foldr function using the State Monad? First checkout the signature of foldr when applied to a list.

this suggest that the state can be modelled as a tuple of a function, a ‘b’ and a list of ‘a’
i.e. foldrS :: (Eq a) => State ((a -> b -> b), b, [a] ) b
And given what we’ve just done I think the implementation is fairly self explanatory:

First we get the state tuple – in particular split the list according to (x:xs). If this is the last element to handle ( xs == [] ) then we call the return function with the result of a final application of the supplied function, f. Otherwise we update the state by applying f x y and reducing the list. Then we recurse. And, finally we have the foldr‘ function which evaluates the state starting with the initial state. 🙂

A couple of examples of the usual foldr and the stateful foldr’ should show the results to be consistent.

Sum of all numbers from 1 to 10.

And the product…

Of course much of this is just an academic exercise but I really found it worthwhile and instructive to do and it helped me understand Monads a bit more and extend, just a little, my horizon into the satisfying world of Haskell coding!

Thanks for reading…