Haskell/Understanding monads/List
Lists are a fundamental part of Haskell, and we've used them extensively before getting to this chapter. The novel insight is that the list type is a monad too!
As monads, lists are used to model nondeterministic computations which may return an arbitrary number of results. There is a certain parallel with how Maybe
represented computations which could return zero or one value; but with lists, we can return zero, one, or many values (the number of values being reflected in the length of the list).
The Monad
instance of lists
edit
The return
function for lists simply injects a value into a list:
return x = [x]
In other words, return
here makes a list containing one element, namely the single argument it took. The type of the list return is return :: a > [a]
, or, equivalently, return :: a > [] a
. The latter style of writing it makes it more obvious that we are replacing the generic type constructor in the signature of return
(which we had called M
in Understanding monads) with the list type constructor []
(which is distinct from, but easy to confuse with, the empty list!).
The binding operator is less trivial. We will begin by considering its type, which for the case of lists should be:
[a] > (a > [b]) > [b]
This is just what we'd expect: it pulls out the values from the list to give them to a function that produces a new list.
The actual process here involves first map
ping a given function over a given list to get back a list of lists, i.e. type [[b]]
(of course, many functions which you might use in mapping do not return lists; but, as shown in the type signature above, monadic binding for lists only works with functions that return lists). To get back to a regular list, we then concatenate the elements of our list of lists to get a final result of type [b]
. Thus, we can define the list version of (>>=)
:
xs >>= f = concat (map f xs)
The bind operator is key to understanding how different monads do their jobs, as its definition specifies the chaining strategy used when working with the monad. In the case of the list monad, the strategy allows us to model nondeterminism: an a > [b]
function can be seen as a way of generating, from an input of type a
, an unspecified number of possible outputs of type b
, without settling on any one of them in particular. (>>=)
, from that perspective, does that for multiple inputs and combines all output possibilities in a single result list.
Bunny invasion
editIt is easy to incorporate the familiar list processing functions in monadic code. Consider this example: rabbits raise an average of six kits in each litter, half of which will be female. Starting with a single mother, we can model the number of female kits in each successive generation (i.e. the number of new kits after the rabbits grow up and have their own litters):
Prelude> let generation = replicate 3 Prelude> ["bunny"] >>= generation ["bunny","bunny","bunny"] Prelude> ["bunny"] >>= generation >>= generation ["bunny","bunny","bunny","bunny","bunny","bunny","bunny","bunny","bunny"]
In this silly example all elements are equal, but the same overall logic could be used to model radioactive decay, or chemical reactions, or any phenomenon that produces a series of elements by repeated multiplication.
Exercises 


Board game example
editSuppose we are modeling a turnbased board game and want to find all the possible ways the game could progress. We would need a function to calculate the list of options for the next turn, given a current board state:
nextConfigs :: Board > [Board]
nextConfigs bd = undefined  details not important
To figure out all the possibilities after two turns, we would again apply our function to each of the elements of our new list of board states. Our function takes a single board state and returns a list of possible new states. Thus, we can use monadic binding to map the function over each element from the list:
nextConfigs bd >>= nextConfigs
In the same fashion, we could bind the result back to the function yet again (ad infinitum) to generate the next turn's possibilities. Depending on the particular game's rules, we may reach board states that have no possible nextturns; in those cases, our function will return the empty list.
On a side note, we could translate several turns into a do
block (like we did for the grandparents example in Understanding monads):
threeTurns :: Board > [Board]
threeTurns bd = do
bd1 < nextConfigs bd  bd1 refers to a board configuration after 1 turn
bd2 < nextConfigs bd1
nextConfigs bd2
If the above looks too magical, keep in mind that do
notation is syntactic sugar for (>>=)
operations. To the right of each leftarrow, there is a function with arguments that evaluate to a list; the variable to the left of the arrow stands for the list elements. After a leftarrow assignment line, there can be later lines that call the assigned variable as an argument for a function. This later function will be performed for each of the elements from within the list that came from the leftarrow line's function. This perelement process corresponds to the `map` in the definition of (>>=)
. A resulting list of lists (one per element of the original list) will be flattened into a single list (the `concat` in the definition of (>>=)
).
List comprehensions
editThe list monad works in a way that has uncanny similarity to list comprehensions. Let's slightly modify the do
block we just wrote for threeTurns
so that it ends with a return
...
threeTurns bd = do
bd1 < nextConfigs bd
bd2 < nextConfigs bd1
bd3 < nextConfigs bd2
return bd3
This mirrors exactly the following list comprehension:
threeTurns bd = [ bd3  bd1 < nextConfigs bd, bd2 < nextConfigs bd1, bd3 < nextConfigs bd2 ]
(In a list comprehension, it is perfectly legal to use the elements drawn from one list to define the following ones, as we did here.)
The resemblance is no coincidence: list comprehensions are, behind the scenes, defined in terms of concatMap
, a function available from the Prelude that is defined as concatMap f xs = concat (map f xs)
. That's just the list monad binding definition again! To summarize the nature of the list monad: binding for the list monad is a combination of concatenation and mapping, and so the combined function concatMap
is effectively the same as >>=
for lists (except for different syntactic order).
For the correspondence between list monad and list comprehension to be complete, we need a way to reproduce the filtering that list comprehensions can do. We will explain how that can be achieved a little later in the Alternative and MonadPlus chapter.
Exercises 

As discussed in Understanding monads, all
