Fork me on GitHub

monads in haskell part 3

Now we have come to the list monad, and now it gets interesting. The list in haskell is viewed as a monad. Why? Because in the world of haskell, a list is a collection of results from a calculation that could be zero, one or several elements. In this view, a calculation with a list is a calculation that is uncertain about the result. It could be zero, i.e an empty list, it could be one entry, i.e a calculation that returns one answer, or it clould be several answers. Confusing? Definitely. It is different view on the list that is a bit challenging. The monad instance for >>= can be defined as follows:

[a] -> (a -> [b]) -> [b]

This tells us that we use a function to manipulate a list to create a new list, or in other words, we submit a list and a function that operates on every element on our list to generate another list. One way to implement >>= is the following:

xs >>= f = concat (map f xs)

Ok. We have a list xs and a function f. What is maybe not so obvious is that the function f must generate a list from a to b and that means that we get a list of lists. So we need to concat thist list of lists, or flatten it. One important thing to understand is that we map on every element. This may make sense if we look at the following example:

[1..10] >>= (\x -> [1..10] >>= (\y -> return (x==y) >>= (\r -> if r then return (x,y) else fail "")))
>>> [(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9),(10,10)]

Here we have a list from 1 to 10. What happens if we just put it in xs=[1..10] and f=(x -> [1..10]) in the definition of >>= above?

concat (map (\x -> [1..10]) [1..10])
>>> [1,2,3,4,5,6,7,8,9,10,
     1,2,3,4,5,6,7,8,9,10,
     1,2,3,4,5,6,7,8,9,10,
     1,2,3,4,5,6,7,8,9,10,
     1,2,3,4,5,6,7,8,9,10,
     1,2,3,4,5,6,7,8,9,10,
     1,2,3,4,5,6,7,8,9,10,
     1,2,3,4,5,6,7,8,9,10,
     1,2,3,4,5,6,7,8,9,10,
     1,2,3,4,5,6,7,8,9,10]

the lamba function gets a list that is applied to all elements in the second argument to map, so the list in the lambda is repeated 10 times, thus giving us a list of lists. concat is then flattening the list. Ok, so this is the same as:

[1..10] >>= \x -> [1..10]

Now I want to pass every element to y:

[1..4] >>= \x -> [1..3] >>= \y -> [1..2]
>>> [1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2]

Here I changed the numbers to avoid to long lists. Ok, we just repeat 1,2 4*3=12 times. Not very exciting but at least we can chain our calculation. Now we want to try to return certain combinations from all combinations, just as we did in the beginning.

[1..4] >>= \x -> [1..3] >>= \y -> return (x==y)

Now I replaced the last list with a condition that x has to be equal to y. And what do we get?

>>> [True,False,False,False,True,False,False,False,True,False,False,False]

return just wraps all the possible results in a list. A list is a monad that can take different values, and we just replaced a list of numbers with a list of booleans. Think of list like a container that contains different values. What does this booleans tell us? Well, they are 12 and 3 of them are true. Lets take a look at the list:

[1..4] >>= \x -> [1..3]
>>> [1,2,3,1,2,3,1,2,3,1,2,3]

ok. so, we repeat [1,2,3] for every element in [1,2,3,4]. And we see that 1==1 in the first comparision, as seen in the Bool list above. Also 1==2 is False and so on. Next True statement is 2==2 and that occurs in the 5:th position in our Bool list. All in all, 3 are True because 4 is not equal to 1,2 or 3. The last step is to show only the relevant combinations and for that we add the following:

[1..4] >>= \x -> [1..3] >>= \y -> return (x==y) >>= \r -> if r then return (x,y) else fail ""
>>> [(1,1),(2,2),(3,3)]

Wow, we just reinvented the wheel in the world of haskell. Haskell rule number one: never think about doing something practical, you are just a visitor in the world of haskell, soon to be on your way back to imperative land.

This is just a little scratch on surface of the list monad and there are some tutorials out there that tries to explain the list monad. This one is very intricate and elegant. And hard to understand.

Comments !