The two faces of Monads

As so many other guys before me, I will try to explain Monads on my “own” way.

In order to explain Monads, I’m gonna show the two faces of them. And I’ll try to avoid using this terrible word - Monad - during this article.

The data structure face

Let’s start with probably the most commonly used data stucture of CS: Lists.

map

In imperative languages we often iterate over Lists and generate new Lists from them. This external iteration can be replace by internal iteration using map method (function).

List[Int] a = List.of(1,2,3,4)
// a = [1,2,3,4]
List[Int] b = a.map(item -> item * 2)
// a = [1,2,3,4]; b = [2,4,6,8]

flatten

Sometimes we encounter cases when a List of Lists should be converted to a single List from that. You can do external iteration again or you can go for a method (function) that does it for you. It is called flatten.

List[List[Int]] a = List.of(List.of[1,2], List.of(3,4), List.of(5,6))
// a = [[1,2],[3,4],[5,6]]
List[Int] b = a.flatten()
// a = [[1,2],[3,4],[5,6]]; b = [1,2,3,4,5,6]

flatMap

Now let’s combine these two. Let’s imagine that we provide map method with a Int -> List[Int] function.

Function[Int, List[Int]] mapper = item -> List.of(item, item * 2)
List[Int] a = List.of(1,2,3,4)
// a = [1,2,3,4]
List[List[Int]] b = a.map(mapper)
// a = [1,2,3,4]; b = [[1,2],[2,4],[3,6],[4,8]]

As we can see b is a perfect input for flatten. So let’s do it.

List[Int] c = b.flatten()
// a = [1,2,3,4]; b = [[1,2],[2,4],[3,6],[4,8]]; c = [1,2,2,4,3,6,4,8]

Now we can put map and flatten together to get flatMap method (function):

Function[Int, List[Int]] mapper = item -> List.of(item, item * 2)
List[Int] a = List.of(1,2,3,4)
// a = [1,2,3,4]
List[Int] b = a.flatMap(mapper)
// a = [1,2,3,4]; b = [1,2,2,4,3,6,4,8]

Now let’s put “data face” with flatMap aside for a minute.

The computation face

I hope you already know Future structure as it will be needed in this chapter.

Future

Future is a structure that “will” hold a value in the future. There is no guarantee when it will have the value. It can be there already or any point in time in the future. This structure is very good to use instead of callbacks. (continuation passing style).

map

As the future does not holds the value currently we can do two things to deal with the data that will be available. 1.) wait for it by blocking the current thread. 2.) map the value to a new value and return a new Future

To demonstrate I am going to use parseInt function, that takes a String and returns a Int.

Let’s imagine that we have a WebService that returns the page hits of our website and our Ajax libarary returns Future instead of taking callbacks.

Future[String] pageHitResponse = Ajax.get("http://localhost/stats/pageHitCounter")
Future[Int] pageHitCounter = pageHitResponse.map(resp -> parseInt(resp))
return pageHitCounter;

Probably you can see now how we can compose functions together using Future.

Future[String] pageHitResponse = Ajax.get("http://localhost/stats/pageHitCounter")
Future[Int] pageHitCounter = pageHitResponse.map(resp -> parseInt(resp))
Future[Int] sexyPageHitCounter = pageHitCounter.map(hits -> hits * 2)
return sexyPageHitCounter;

That is the same as:

Future[String] pageHitResponse = Ajax.get("http://localhost/stats/pageHitCounter")
Future[Int] pageHitCounter = pageHitResponse.map(resp -> parseInt(resp)).map(hits -> hits * 2)
return sexyPageHitCounter;

Or:

Future[String] pageHitResponse = Ajax.get("http://localhost/stats/pageHitCounter")
Future[Int] sexyPageHitCounter = pageHitResponse.map(resp -> parseInt(resp) * 2)
return sexyPageHitCounter;

flatten

Let’s make a step forward. Imagine a sport data service where you can get match, team, etc. information. Unfortunately the match response doesn’t contain the name of the teams. The name can be looked up from the team service. Let’s implement is quickly.

function Future[String] homeTeamName(String matchId)
    Future[Match] matchFut = Ajax.get("http://localhost/matches/${matchId}").map(resp -> parseMatch(resp))
    Future[Future[String]] homeTeamNameFut = matchFut.map(match -> Ajax.get("http://localhost/teams/${match.homeTeamId}").map(resp -> parseTeam(resp)).map(team -> team.name))
    // opsssss.....

We expect a Future[String] but we have only a Future[Future[String]]. Hold on! This reminds me for what we seen already when we discussed Lists. Can we do the same? Of course we can.

function Future[String] homeTeamName(String matchId)
    Future[Match] matchFut = Ajax.get("http://localhost/matches/${matchId}").map(resp -> parseMatch(resp))
    Future[Future[String]] homeTeamNameFut = matchFut.map(match -> Ajax.get("http://localhost/teams/${match.homeTeamId}").map(resp -> parseTeam(resp)).map(team -> team.name))
    return homeTeamNameFut.flatten()

flatMap (bind)

What if we put map and flatten together again:

function Future[String] homeTeamName(String matchId)
    return Ajax.get("http://localhost/matches/${matchId}")
            .map(resp -> parseMatch(resp))
            .flatMap(match -> Ajax.get("http://localhost/teams/${match.homeTeamId}").map(resp -> parseTeam(resp).name))

Task

Future is just a data structure, that encapsulates the result of a computation. If we make one more step further, we can devise another structure that encapsulates not just the result but the computation itself as well. We will call it Task. Task is a computation that will hold a certain type of result when after it’ll have been executed.

eg.:

Task[String] pageHitTask = Ajax.getTask("http://localhost/stats/pageHitCounter")
String pageHitCounter = pageHitTask.execute()

The big difference between Future and Task that Task can be executed as many times as you wish. As we discussed before it encapsulated the whole computation. On the other hand Future encapsulated only the result of a computation.

map

Can we map over this type? Let’s try it.

Task[String] pageHitStrTask = Ajax.getTask("http://localhost/stats/pageHitCounter")
Task[Int] pageHitIntTask = pageHitStrTask.map(resp -> parseInt(resp))

Certainly it should work.

flatten

What about flatten?

Task[Match] matchTask = Ajax.getTask("http://localhost/matches/${matchId}").map(resp -> parseMatch(resp))
Task[Task[String]] homeTeamNameTaskTask = matchTask.map(match -> Ajax.getTask("http://localhost/teams/${match.homeTeamId}").map(resp -> parseTeam(resp)).map(team -> team.name))
Task[String] homeTeamNameTask = homeTeamNameTaskTask.flatten();

flatMap (bind)

Probably you can already see that flatMap is straigthforward on Tasks.

Task[Match] matchTask = Ajax.getTask("http://localhost/matches/${matchId}")
                            .map(resp -> parseMatch(resp))
Task[String] homeTeamNameTask = matchTask.flatMap(match -> Ajax.getTask("http://localhost/teams/${match.homeTeamId}")
                                                               .map(resp -> parseTeam(resp))
                                                               .map(team -> team.name)
                                                 )

Hmmm… Flat Map… this is not a data structure. We are not really mapping the data here. We only compose two computation. Can we find a better name?

Haskell guys decided to call flatMap bind (>>=) as it fits more to the composition concept.

Task[String] hoemTeamNameTask = Ajax.getTask("http://localhost/matches/${matchId}")
                                    .map(resp -> parseMatch(resp))
                                    .bind(match -> Ajax.getTask("http://localhost/teams/${match.homeTeamId}")
                                                       .map(resp -> parseTeam(resp).name)

Monads

All the above are Monads. The most important bit of Monads is the bind (or flatMap) function. This function must obey to certain monadic rules, but I suggest not to be bothered by those laws for now. Until you start writing Monads you won’t be in need for them.

IOTask in Haskell

Sorry… I mean IO Monad…

Disclaimer: In this chapter I’m gonna use “IO Task” instead of the offical name: IO Monad.

Haskell is a purely functional languages. It means that you can not have side-effects in your code. Unfortunately our world is about side effects. But Haskell found a way around it.

If you check Haskell’s main function and compare it with - let’s say - C’s main function, you will see something very strange.

-- Takes nothing and returns a IO Task that will hold nothing at the end.
main :: IO ()

-- Takes arguments and returns exit code
int main(int argc, char *argv[])

I don’t provide you access to the arguments and it doesn’t expect an exit code to be returned. Haskell’s main function is just AN IO TASK. This IO Task will be executed by Haskell runtime. In Haskell you can not call execute on IO task at all. It’s visible for you. It can be called by Haskell runtime only.

That still doesn’t explain how side effect is done. Haskell provides a couple of built in IO Tasks. Eg.

• getLine that is a IO String,
• putStr that takes a String and returns an IO ()
• etc.

In the previous chapter we learnt how to put Tasks together using bind function. So we now know how to compose these building blocks in order to build echo program:

// These are provided by the language:
// Task[String] getLine
// Function[String, Task[None]] putStr
Task[None] main = getLine bind putStr

In Haskell bind is done by >>= function.

main :: IO ()
main = getLine >>= putStr

Life without map

I have bad news. Monads don’t have map function.* Let’s see how can we live without map.

Let’s go back to Lists to find some solution.

List[Int] a = List.of(1,2,3,4).map(item -> item * 2)
// a = [2,4,6,8]

Can we do the same only using flatMap? Certainly we can if we generate single element lists in the flatMap.

List[Int] a = List.of(1,2,3,4).flatMap(item -> List.singleItemListOf(item * 2))

What about Future? Can we live without map?

Future[Int] pageHitCounter = Ajax.get("http://localhost/stats/pageHitCounter").map(resp -> parseInt(resp))

We somehow must wrap the result of parseInt into a Future. That shouldn’t be a problem. A Future with immediate result “will” still have the value in the future.

Future[Int] pageHitCounter = Ajax.get("http://localhost/stats/pageHitCounter").flatMap(resp -> ImmediateFuture(parseInt(resp)))

And the Task? Can we do the same with Task?

Task[Int] pageHitIntTask = Ajax.getTask("http://localhost/stats/pageHitCounter").map(resp -> parseInt(resp))

Certainly we can. A Task that doesn’t do any computation just returns a value is certainly a Task. Let’s call it Unit.

Task[Int] pageHitIntTask = Ajax.getTask("http://localhost/stats/pageHitCounter").flatMap(resp -> Unit(parseInt(resp)))

In all three cases above, we needed a “constructor” to be able to live without map. Fortunately, this “constructor” is supported by Monads, called unit function.

So let’s do a bit more complex example. I’m gonna read a line from standard input, parse it as an int, multiply it by 2 and print out the result.

// These are provided by the language:
// Task[String] getLine
// Function[String, Task[None]] putStr
// Function[String, Int] parseInt
// Function[Int, String] toString
// Function[T, Task[T]] unit
Task[String] a = getLine
Task[Int]    b = a bind (line -> unit(parseInt(line)))
Task[Int]    c = b bind (inp  -> unit(inp * 2))
Task[String] d = c bind (res  -> unit(toString(res)))
Task[None]   e = d bind (out  -> putStr(out))

Let’s put everything into one line:

Task[None] main = getLine bind (line -> unit(parseInt(line))) bind (inp  -> unit(inp * 2)) bind (res  -> unit(toString(res))) bind (out  -> putStr(out))

Clean it up a bit:

Task[None] main = getLine bind (line -> unit(toString(parseInt(line) * 2))) bind putStr

Unit is called return in Haskell (in order to support do notation syntax that I’m not gonna discuss here).

main :: IO ()
main = getLine >>= (\x -> return $ toString $ (*2) $ parseInt x)  >>= putStr

or using composition:

main :: IO ()
main = getLine >>= return . toString . (*2) . parseInt  >>= putStr

* I was cheating when I said Monads don’t support map. Though Monads don’t have map by definition, in practice Monad implementations (List, Maybe, IO Task) provide map and you don’t need to worry about it.