Haskell/Understanding monads/List

From Wikibooks, open books for an open world
Jump to: navigation, search

Lists are commonplace in Haskell, and you surely have used them extensively before getting to this chapter. What is novel here is that the list type, [] a, is a monad too. Taken 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; the difference being that through lists zero, one or many values can be returned (the number of values being reflected in the length of the list).

Instantiation as monad[edit]

The implementation of the return function, that injects a generic value into a list, is quite simple:

return x = [x]

In other words, injecting a value into a list means making a list containing that value only. 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) by the list type constructor [] (do not confuse the latter with the empty list!).

The binding operator is a little less trivial. We will begin by considering its type, which for the case of lists should be:

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

That is, from a list of a-type values and a function producing lists of b-type values from each a-type one, we get a list of b's. Now, mapping the function over the list of a's would give [[b]], a list of lists of b's. By using concat to concatenate the elements of this list of lists we get a list of b's - and a definition of (>>=):

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

The bind operator is always key to understanding how a monad does its job, for it implements the chaining strategy which is responsible for making the monad useful. In the case of the list monad, the type of the function to the right of (>>=) brings non-determinism into play, as evaluating to a list for each value corresponds in effect to giving back a variable number of results for each value passed to the function. map in turn applies f to all values from the xs computation, leaving us with potentially many results for each element of xs. Finally, concat combines all of these results in a simple list of type [b], thus ensuring that the type of the final computation matches the signature of (>>=) and therefore that we can proceed with chaining it to other list computations.

Bunny invasion[edit]

To begin with, a simple example showing that it is easy to incorporate the familiar list processing functions in monadic code. A rabbit couple can spawn six rabbits every month. Considering half of them will be females, we can model the number of female rabbits after a certain number of generations using a function like:

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 trivial example all elements are equal, but one could for example model radioactive decay or chemical reactions, or any phenomena that produces a series of elements starting from a single one.

Noughts and crosses[edit]

Suppose we are modelling the game of noughts and crosses (known as tic-tac-toe in some parts of the world). An interesting (if somewhat contrived) problem might be to find all the possible ways the game could progress: find the possible states of the board 3 turns later, given a certain board configuration (i.e. a game in progress). The problem can be boiled down to the following steps:

  1. Find the list of possible board configurations for the next turn.
  2. Repeat the computation for each of these configurations: replace each configuration, call it C, with the list of possible configurations of the turn after C.
  3. We will now have a list of lists (each sublist representing the turns after a previous configuration), so in order to be able to repeat this process, we need to collapse this list of lists into a single list.

This structure should look similar to the monad instance for list described above. Here's how it might look, without using the list monad (concatMap is a shortcut for when you need to concat the results of a map: concatMap f xs = concat (map f xs)):

nextConfigs :: Board -> [Board]
nextConfigs = undefined -- details not important
 
tick :: [Board] -> [Board]
tick bds = concatMap nextConfigs bds
 
thirdConfigs :: Board -> [Board]
thirdConfigs bd = tick $ tick $ tick [bd]

concatMap, however, is just the bind operator for lists, only with the arguments in reversed order; and so we can write a literal translation of thirdConfigs using the list monad:

thirdConfigs :: Board -> [Board]
thirdConfigs bd = return bd >>= nextConfigs >>= nextConfigs >>= nextConfigs

Alternatively, we can write the above as a do block - compare the translation with what we did for the grandparents example in Understanding monads:

thirdConfigs :: Board -> [Board]
thirdConfigs bd = do
  bd0 <- return bd       -- Initial configuration
  bd1 <- nextConfigs bd0 -- After one turn
  bd2 <- nextConfigs bd1 -- After two turns
  nextConfigs bd2        -- After three turns

Note how the left arrow in the list monad, in effect, means "do whatever follows with all elements of the list on the right of the arrow". That effect is due to the mapping performed by the bind operator.

We can simplify the monadic code a bit further by noting that using return bd to get a list with a single element and then immediately extracting that single element with the left arrow is redundant:

thirdConfigs :: Board -> [Board]
thirdConfigs bd = do
  bd1 <- nextConfigs bd
  bd2 <- nextConfigs bd1
  nextConfigs bd2

Short and sweet, with the plumbing formerly done by the tick function now wholly implicit.

List comprehensions[edit]

One thing that can be helpful in visualizing how the list monad works is its uncanny similarity to list comprehensions. If we slightly modify the do block we just wrote for thirdConfigs so that it ends with a return...

thirdConfigs bd = do
  bd1 <- nextConfigs bd
  bd2 <- nextConfigs bd1
  bd3 <- nextConfigs bd2
  return bd3

... it mirrors exactly the following list comprehension:

thirdConfigs 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, like we did here.)

The resemblance is no coincidence: list comprehensions are, behind the scenes, also defined in terms of concatMap. For the correspondence to be complete, however, there should be a way to reproduce the filtering that list comprehensions are capable of. We will explain how that can be achieved a little later, in the Additive monads chapter.