Learning Monads in an Example

I have been struggling with the concept of monads for a long time, and since I am writing my bachelor thesis in Haskell, it was about time to face this problem head-on, not by only using one of the provided monads but to trying to implement on of my own. Since I am not an expert in the field, I have to recommend you some previous literature that might help you more than I will:

• Learn You a Haskell for Great Good is a super fun book for beginners in Haskell that you can read online. It has chapters on functors and monads.
• Philip Wadler’s papers on monads for functional programming, that explain the basic concepts of monads and goes through the main types of monads.

If you have already read this but you are not sure yet on how to implement a monad in Haskell, maybe this little example will help you and you will save visiting some of the dead ends I had to face.

Once again I am not an expert, so feel free to open an issue to give any kind of feedback: improvements of the explanation, corrections on concepts, better tips, more literature… Thank you, dear reader!

An example: Euclidean Algorithm

A pure approach

One of the easiest and prettiest examples to program in Haskell is the Euclidean Algorithm to find the Greatest Common Divisor of two given numbers. We can see the code for that function here:

simpleGCD :: (Integral a) => a -> a -> a
simpleGCD a b
  | a < b          = simpleGCD b a
  | a `mod` b == 0 = b
  | otherwise      = simpleGCD b (a `mod` b)

This function receives to integer numbers, and computes their remainder operation recursively until 0 is found. This codes exhibits and it works like a charm:

λ> simpleGCD 9282 12376
3094
(0.01 secs, 4128256 bytes)
λ> simpleGCD 9293 12376
1
(0.01 secs, 4129080 bytes)

However, what if we want to get a trace of the execution performed? In a different language like Python we could think of printing the steps in each iteration, but that implies secondary effects and is not that easy to do something like that in a purely functional environment like the one Haskell offers. Another option is to create a type Log, that contains both the value and the a list of strings:

data Log a = Log { getValue :: a, getLogs :: [String] } deriving Show

In that list of strings, we can add each of the steps performed in the recursive call, but that will create a huge mess and the code will be barely readable. What we can do is to check if it makes sense to implement Log as a monad.

Turning Log into a monad

In Haskell, for a type to be a monad it has to be also a functor and applicative. Don’t worry though, all monads are by definition functor and applicatives, so if you really need to turn your data into a monad there will be no problem. It is a healthy exercise to check if your data makes sense as a monad.

To make a Log an instance of the Functor class, we need to define its behavior with fmap:

instance Functor Log where
  fmap f (Log x logs) = Log (f x) logs

Here, we define that every time that a function f :: a -> b is mapped to a Log a, we want to apply it to the value and let the list of logs as it is. Next step is to define the data as Applicative, which implies the next functions:

instance Applicative Log where
  pure x = Log x []
  Log f log <*> Log x log' = Log (f x) (log ++ log')

Where we define that pure can turn a value into a Log by creating an object with that value and an empty list of logs. The <*> operator seems a little bit more obscure, but in case there is a function contained in a Log it should be appended to the value of another Log and both lists of logs should be appended. This makes perfect sense when we think about the creation of partial functions in Haskell.

Finally, we are able now to make Log an instance of Monad. To do so, we must define:

instance Monad Log where
  return = pure
  (Log x log) >>= f = let Log y new = f x in Log y (log ++ new)

return is used to include a new value in a Log, so we can reuse the definition of pure. On the other hand, the bind operator (>>=) defines the behavior we have been trying to achieve: every time we want to bind a Log object to the results of a function that takes the value of a Log and returns a new log, we take the value returned by the function but we append the logs of the new function to the list of the old ones.

Although it may seem strange to do it like so (using >>=), we need to notice that this is the real operators that a do-block uses as syntactic sugar; taking this into account we could create a function to store the new logs in a dummy Log before being appended to the object by the end of recursion:

saveLog :: String -> Log ()
saveLog str = Log () [str]

Although this function may seem unnecessary (and it kind of is), it provides a cleaner syntax and it is actually replicated in the provided Writer monad as tell.

Using all these pieces, we can finally update the algorithm to perform the logging of operations! In each guard (except the swapping one) we just need to create a do-block were we log a message and then bind a value to that block. The final version of the function is:

logGCD :: (Integral a, Show a) => a -> a -> Log a
logGCD x y
 | x < y = logGCD y x
 | y == 0 = do
     saveLog $ "Greatest Common Divisor found: " ++ show x
     return x
 | otherwise = do
     saveLog $ show x ++ " mod(" ++ show y ++ ") = " ++ show (x `mod` y)
     logGCD y (x `mod` y)

We can try the function with the stepsGCD function that will print all the logs in a nice way:

λ> stepsGCD 9282 12376
12376 mod(9282) = 3094
9282 mod(3094) = 0
Greatest Common Divisor found: 3094
(0.01 secs, 2575200 bytes)
λ> stepsGCD 9293 12376
12376 mod(9293) = 3083
9293 mod(3083) = 44
3083 mod(44) = 3
44 mod(3) = 2
3 mod(2) = 1
2 mod(1) = 0
Greatest Common Divisor found: 1
(0.01 secs, 2575400 bytes)

We can see how now the trace is nicely printed, and we have only modified the GCD function as much as we would have done it in an imperative language. Monads principle advantage is modularity, that helps us isolate the secondary effects keeping the purity.

The Monad laws

It is really important to understand that the monad type comes with some laws that your type has to fulfill. These laws are:

• The left-identity: Basically, that return x >>= f should have the exact same result as f x. By trying our type with logGCD:

λ> return 3 >>= (logGCD 5)
Log {getValue = 1, getLogs = ["5 mod(3) = 2","3 mod(2) = 1","2 mod(1) = 0",
"Greatest Common Divisor found: 1"]}
λ> (logGCD 5) 3
Log {getValue = 1, getLogs = ["5 mod(3) = 2","3 mod(2) = 1","2 mod(1) = 0",
"Greatest Common Divisor found: 1"]}

• The right-identity: Similar to the previous one, m >>= return should be equal to m.

λ> let m = logGCD 5 3
λ> m
Log {getValue = 1, getLogs = ["5 mod(3) = 2","3 mod(2) = 1","2 mod(1) = 0",
"Greatest Common Divisor found: 1"]}
λ> m >>= return
Log {getValue = 1, getLogs = ["5 mod(3) = 2","3 mod(2) = 1","2 mod(1) = 0",
"Greatest Common Divisor found: 1"]}

• The associativity law, that states that a chain of monadic operations should not be dependant on its nesting.

λ> return 14 >>= (logGCD 35) >>= (logGCD 21)
Log {getValue = 7, getLogs = ["35 mod(14) = 7","14 mod(7) = 0",
"Greatest Common Divisor found: 7","21 mod(7) = 0",
"Greatest Common Divisor found: 7"]}
λ> ( return 14 >>= (logGCD 35) ) >>= (logGCD 21)
Log {getValue = 7, getLogs = ["35 mod(14) = 7","14 mod(7) = 0",
"Greatest Common Divisor found: 7","21 mod(7) = 0",
"Greatest Common Divisor found: 7"]}
λ> return 14 >>= (\x -> ((logGCD 35) x) >>= (logGCD 14))
Log {getValue = 7, getLogs = ["35 mod(14) = 7","14 mod(7) = 0",
"Greatest Common Divisor found: 7","14 mod(7) = 0",
"Greatest Common Divisor found: 7"]}

Because yes, thanks to the Monad value, we can chain GCD operations to obtain combined logs. Super cool, isn’t it?

Do I really have to do all this?

Actually, no. This was just an example on how to build a super simple monadic type, but it is so simple and common that Haskell provides you with its own implementation, Control.Monad.Writer. If you ever feel like you need it in the real world, don’t reinvent the wheel and just use the provided one. However, take also into account that if you need high-performant computations, the overhead generated by Writer may be too high and it may be worth to check other packages (like fast-logger) or implement your own monad.

Also, even though I said that it is a healthy exercise to think if your data is as well a functor and applicative, but that is indeed not necessary either. If you are struggling with it, you can use the functions provided by the Monad class to define Functor and Applicative instances like this:

import Control.Monad (liftM, ap)

instance Functor Log where
  fmap = liftM

instance Applicative Log where
  pure  = return
  (<*>) = ap

And then just focus on defining the Monad instance. There might be a more efficient way to define it, but this should work anyway for all cases. Just be sure of checking if the data really makes sense as a monad before actually implementing it as such.

Further reading

After understanding this, it is probably useful to read:

• “A tour of the Haskell Monad functions” by Henk-Jan van Tuyl, that describes the different functions that the Monad class offers in Haskell.