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

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 mapping 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 non-determinism: 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

It 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
Predict what should be the result of ["bunny", "rabbit"] >>= generation. Implement themselvesTimes :: [Int] -> [Int], which takes each number $n$ in the argument list and generates $n$ copies of it in the result list.

Board game example

Suppose we are modeling a turn-based 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 next-turns; 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 left-arrow, 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 left-arrow 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 left-arrow line's function. This per-element 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

The 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 Monads also have an instance of Applicative. In particular, (<*>) for that instance might be defined as: fs <*> xs = concatMap (\f -> map f xs) fs Explain briefly what this (<*>) does. Write an alternative definition of (<*>) using a list comprehension. Do not use map, concat or concatMap explicitly.