# Haskell lottery: a nice and easy example of monads and monad transformers

My humble understanding of monads in Haskell began some years ago, when I heard that IO was a Monad (whatever that was)… Despite hearing the dreaded “M” word, I wasn’t much scared and carried on programming my little Haskell programs, using `putStrLn`

, `getLine`

, `readFile`

, `writeFile`

and etc. Then, in my 3rd year in college, I decided to implement a graphical app for manipulating finite automata, using GTK (Gtk2Hs). During the development of this program, a huge part of my functions started to get “infected” with `IO`

in their types, so I thought it would be a nice idea to think a bit deeper about this “Monad” thing.

At that time I discovered that there are A LOT of monads in Haskell, and that A LOT of them are useful and popular - even though you might not know that they are monads… There is the State Monad, Parser monads, Reader and Writer monads, the Error monads, the Either Monad, the Maybe Monad and even the List Monad!!! YES! `Maybe a`

and `[a]`

are monads! :D Well, “all of these things are monads, that’s very nice, but why should I care?”, you might ask. I hope to give you just a bit of an answer with the example in this post.

In this post, I will assume that you have at least some experience with Haskell, and that you have messed around with at least IO (maybe with Maybe too, hun? :P)…

So, every year we have a tradition in Brazil, which is a big lottery run on December 31st, with a huge prize. This year my family bought 180 tickets, and I wrote a program to check if any of them had the winning numbers shown on TV. I wrote this program in Haskell - of course - and this time I was forced to deepen my understanding of monads AND monad transformers to get it done.

The program should work as follows: A file containing all 180 tickets (each with 6 numbers) must be read. Then 6 rounds of input happen: in each round, the user types a number and the program matches the collection of typed numbers with all tickets. Then, the 5 tickets with the biggest amount of `lucky`

numbers are printed on the screen. Again, six of these “rounds” must happen.

I started modelling my program from the bottom-up, by defining a datatype to represent a lottery ticket, a `Combination`

of lottery numbers:

Notice that a Combination has two sets of ints, a `lucky`

and an `unlucky`

one. The lucky one contains the numbers belonging to this combination that “showed up” on TV, while the unlucky ones are the rest… Also, the Ord instance for Combination is interesting: a combination is **larger** than another if the size of it’s lucky set is bigger. I use `(flip compare)`

there just to make clearer that we are defining the notion of “larger” instead of “lesser or equal” (more common).

I then proceeded to implement the parsing of the file into a list of Combination. This part is a bit out-of-context in this post, but I tried to make nice use of monadic features *even here*:

Comparing the types of `makeCombination`

and `makeCombinations`

, for example, you see that they have **a lot in common**. I think that most people would implement makeCombinations as `makeCombinations = map makeCombination`

. I just used liftM to make very clear that List is a Monad. Thus, we are lifting the `makeCombination`

function **into the List Monad**. Then, at the definition of `readCombinations`

, we have to use `liftM`

again, but this time we **lift into the IO Monad**. So we use `liftM makeCombinations`

. The expression `liftM makeCombinations`

has type `IO [[Int]] → IO [Combination]`

, and `readMatrix`

has type `FilePath → IO [[Int]]`

, so the types match nicely and allow an elegant composition, like this :)

`(FilePath → IO [[Int]]) ∘ (IO [[Int]] → IO [Combination]) ≡ (FilePath → IO [Combination])`

Going further down the code, we reach the “core” function of our lottery checker: a function called `matchWithCombination`

, which takes a `probe`

(a number that showed up on TV) and one combination, returning a new combination with its lucky and unlucky components updated in case of a `match`

with the probe:

We use IntSet.intersection to “match” the probe with the unlucky numbers, then update the current lucky set, by uniting it with the new lucky guy. The definition of `matchWithCombination`

also shows a nice syntactical feature of Haskell: allowing us to both define AND use functions in **infix** form, by just putting backticks around the function name. Well.. we now define matchWithCombinations, very obviously: it’s ALMOST just a map (a lift to the List Monad), but we need to keep the probe argument as it is (unlifted), so that’s why the partial application:

Our program is now quite full-featured. Using matchWithCombinations, we can already take a number and see where it appears on all tickets. Two of the requirements we defined earlier are lacking, though:

- We need input (the user needs to
**type in**the numbers in the terminal) and output (print the top 5 tickets on the terminal) - We need to perform 6 (input → process → output) “rounds”

Our `matchWithCombinations`

function can only do ONE “update” step, so we need to keep “threading” the results of calls to it in a chain, like this (sort of):

`(matchWithCombinations <user-input> (matchWithCombinations <user-input> (matchWithCombinations <user-input> originalCombs)))`

Usually, to accomplish this sort of “threading of a state” between function calls, we use the (obviously named) State Monad. And, as you might have already guessed, to perform input and output, we use the almighty **IO Monad**. It’s nice to see how each “layer of functionality” in your program corresponds to a layer in the **“Monad onion”** that your program becomes. So here we need to **combine** State and IO, two monads… Keep this in mind.

In a slight detour of our monad-combining craze, let me introduce you to the simple and humble `askForNewNumber`

monad (a function in the IO Monad). Its task is to read a line of input from the terminal and (do its best) to convert it to an Int:

Now we want to use `askForNewNumber`

in a more sophisticated monad, called `includeNewNumber`

. The `includeNewNumber`

monad will keep a **state** consisting of our combination list, and will (each time it’s called) read a number from the terminal and update the state with the newly matched combinations. The type of `includeNewNumber`

has to be a combination of IO (because it uses `askForNewNumber`

) and State. But how can we combine two monads??

Well, the good news is that we can usually combine two monads into **another monad**, by using this nifty thing called **“monad transformers”** :P In our case, we want to “transform” mere IO into a `State IO`

. Look at the beautiful definition of `includeNewNumber`

by yourself:

Literally, the type of `includeNewNumber`

is `StateT [Combination] IO ()`

, which means that we applied the **“State Transformer”** to the IO Monad, the type of our state being `[Combination]`

and the type returned by IO being () (the unit type). StateT “wraps” IO with a layer of State, so now our program “onion” has officially two layers of functionality! Nice, hun!? :D Before going on, just one little explanation: **IO must always be the innermost layer**, mainly because when running the program all other layers are “peeled off”, and `IO ()`

is what we need to give to `main`

. The task of “peeling off” IO itself lays with the Haskell runtime system, and is out of our control :)

In the body of `includeNewNumber`

, we need again to lift `askForNewNumber`

, so that it resides on the outer StateT layer. After getting the probe we modify the state held by the monad using `matchWithCombinations probe`

. Now we are VERY close to getting this program DONE®. In fact, we are so close that we could now run `includeNewNumber`

six times… the numbers would be read and the combination list would be updated correctly; the only problem is that nothing would show up on the screen :(

Of course we are going to implement the last requirement (print the top 5 combinations after each round), but this optionality shows that monads (and monad transformers) allow you to write software in a very **composable** way, in which independent features are implemented in independent code. A very high Separation of Concerns indeed. Let’s go on then with the implementation of our “feature full” function: `includeAndPrintTop5`

We first include a new number and get the (already updated) combinations state into `combs`

. Then we pass `combs`

through a pipeline which will print the top 5 combs on the screen. At the end of the pipeline, we need `lift`

again, to transform the `IO ()`

returned by putStrLn into the desired `StateT [Combination] IO ()`

.

Dear reader, **behold!** Now comes the end of this post: I will show you the implementation of `main`

for the lottery program…. With 2 lines of code! :)

First things first: we read the file into the suggestively-named `initial`

value. We also need to perform 6 rounds of `includeAndPrintTop5`

. That’s what `replicateM_ 6`

is doing for us. If you want, you can do this repetition manually, like this:

```
execStateT (includeAndPrintTop5 » includeAndPrintTop5 » includeAndPrintTop5 »
includeAndPrintTop5 » includeAndPrintTop5 » includeAndPrintTop5 » return ()) initial
```

Finally, we use execStateT to “peel off” the State Transformer and leave the rest of the job to our friend, IO (). The arguments to execStateT are the state monad it needs to “exec” and an initial state. It then runs the monad and doesn’t care about what is returned (in case you want the returned value, `evalStateT`

is for you).

DONE! TA-DA! :D Please, do not believe my black magic. Grab the code on my “katas” GitHub repository https://github.com/joaopizani/katas and run for yourself, then change it and play with it… Have fun :)

PS:

If you played with lists before (you should have), you will know the

`replicate`

function from`Data.List`

… Indeed,`replicateM_`

and`replicate`

work VERY similarly. Take a look (≡ means “is equivalent to”):`replicate 6 1 ≡ 1 : 1 : 1 : 1 : 1 : 1 : [] replicateM_ 6 m ≡ m » m » m » m » m » m » (return ())`

Now you can already start to imagine how List is a monad, can’t you? ;)

- If you want to really know how
`1 : 1 : 1 : []`

and`m » m » m » (return ())`

are related, take a look at the source code. Seriously, it’s HERE.