Haskell/Understanding monads/List

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

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).

List instantiated as monad[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) by 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 value from the list to give to a function that returns 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, and its definition indicates the chaining strategy for working with the monad.

For the list monad, non-determinism is present because different functions may return any number of different results when mapped over lists.

Bunny invasion[edit]

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 phenomena that produces a series of elements starting from a single one.

Board game example[edit]

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 to 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.[1]

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[edit]

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

The resemblance is no coincidence: list comprehensions are, behind the scenes, defined in terms of concatMap and 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 Additive monads chapter.

  1. As an optional advanced exercise: research how we could do recursive binding to find all possible results for games that have a finite number of possibilities. Furthermore, consider how we might handle the empty list results when they are reached and still retain the list of possible final actual board states.