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.
1 2 3 4 |
-- sumList :: [Int] -> Int sumList [] = 0 sumList (x:xs) = x + sumList xs |
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
1 2 |
sumListS :: State (Int, [Int]) Int sumListS = undefined |
For the moment the implementation is undefined and we can write the following function that will compile.
1 2 |
sumList' :: [Int] -> Int sumList' xs = evalState sumListS (0, xs) |
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.
1 2 3 4 5 6 7 8 9 10 |
-- sumListS :: State (Int, [Int]) Int sumListS = do (sm, (x:xs)) <- get if xs == [] then return (sm +x) else do put (sm + x, xs) sumListS |
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
1 2 |
-- put (sm + x, xs) >>= \_ -> sumListS |
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
1 2 |
-- put (sm + x, xs) >> sumListS |
Also the line (sm, (x:xs)) <- get can be written as get >>= \(sm, (x:xs)) -> ….
So, using bind notation the completed function is
1 2 3 4 5 6 7 8 9 |
-- sumListS :: State (Int, [Int]) Int sumListS = get >>= \(sm, (x:xs)) -> if xs == [] then return (sm +x) else put (sm + x, xs) >> sumListS sumList' :: [Int] -> Int sumList' xs = evalState sumListS (0, xs) |
How about the factorial function?
Here’s a simple implementation
1 2 3 4 |
-- fact :: Int -> Int fact 0 = 1 fact n = n * fact (n -1) |
And in State Monad style this becomes
1 2 3 4 5 6 7 8 9 |
-- factS :: State Int Int factS = get >>= \x -> if x == 0 then return 1 else put (x - 1) >> fmap (*x) factS fact :: Int -> Int fact = evalState factS |
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.
1 2 |
-- foldr :: (a -> b -> b) -> b -> [a] -> b |
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:
1 2 3 4 5 6 7 8 |
-- foldrS :: (Eq a) => State ((a -> b -> b), b, [a] ) b foldrS = get >>= \(f, y, (x:xs)) -> if xs == [] then return $ f x y else put (f, f x y, xs) >> foldrS foldr' f y xs = evalState foldrS (f, y, xs) |
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.
1 2 3 4 5 6 7 |
-- λ-> foldr (+) 0 [1..10] 55 *Main λ-> foldr' (+) 0 [1..10] 55 *Main |
And the product…
1 2 3 4 5 6 7 |
-- λ-> foldr (*) 1 [1..10] 3628800 *Main λ-> foldr' (*) 1 [1..10] 3628800 *Main |
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…