diego-vicente/monadic-gcd

#+Title: Learning Monads in an Example
#+Author: Diego Vicente Martín
#+Email: diegovicente@protonmail.com

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:

• [[http://learnyouahaskell.com/][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.
• [[http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf][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
[[https://en.wikipedia.org/wiki/Euclidean_algorithm][Euclidean Algorithm]] to find the Greatest Common Divisor of two given
numbers. We can see the code for that function here:

#+BEGIN_SRC haskell
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)
#+END_SRC

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:

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

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:

#+BEGIN_SRC haskell
data Log a = Log { getValue :: a, getLogs :: [String] } deriving Show
#+END_SRC

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:

#+BEGIN_SRC haskell
instance Functor Log where
fmap f (Log x logs) = Log (f x) logs
#+END_SRC

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:

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

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:

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

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:

#+BEGIN_SRC haskell
saveLog :: String -> Log ()
saveLog str = Log () [str]
#+END_SRC

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:

#+BEGIN_SRC haskell
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)
#+END_SRC

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

#+BEGIN_SRC
λ> 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)
#+END_SRC

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:

#+BEGIN_SRC
λ> 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"]}
#+END_SRC

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

#+BEGIN_SRC
λ> 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"]}
#+END_SRC

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

#+BEGIN_SRC
λ> 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"]}
#+END_SRC

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 [[https://hackage.haskell.org/package/fast-logger][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:

#+BEGIN_SRC haskell
import Control.Monad (liftM, ap)

instance Functor Log where
fmap = liftM

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

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:

• [[http://members.chello.nl/hjgtuyl/tourdemonad.html]["A tour of the Haskell Monad functions" by Henk-Jan van Tuyl]], that describes
  the different functions that the Monad class offers in Haskell.