Monadic List Functions

We have one more monad to talk about, a really important one: IO lets us finally write complete programs, because it provides our program with the ability to talk to the outside world, to read input and write output. Before tackling this monad though, the next two sections talk about helpful abstractions for working with lists and other containers using monads.

In List Functions, we talked about standard functions to manipulate lists, such as map, filter, zip, foldl, etc. We can think about these functions as iteration functions, functions that do things that we usually accomplish using loops in imperative languages: map applies a function to every element in a list and returns the list of results. filter collects all the elements in a list that match some condition. zip combines two lists into a single list. And foldl captures the concept of accumulating all elements in a list into a single value, such as summing up all the numbers in a list.

When applying some transformation to each element in a list using a loop in an imperative language, the loop can maintain some state, and this state can alter the nature of the transformation. The map function can do no such thing, because the function it applies to every list element is a pure function. Here is a simple example of such a stateful transformation. Let's say we have a list of numbers and we want to replace each number with the average of the numbers in the list up to this point:

runningAverages :: [Double] -> [Double]

GHCi

>>> runningAverages [1,2,3]
[1.0,1.5,2.0]

The first value in the result is the average of 1. The second value is the average of 1 and 2. The third value is the average of 1, 2, and 3.

Here is how we would do this in Python:

def running_averages(xs):
    total = 0
    count = 0
    averages = []
    for x in xs:
        total += x
        count += 1
        averages.append(total / count)
    return averages

The state maintained by the loop is the current total and count. Each iteration of the for-loop updates this state and uses it to compute the next element to be added to the averages list. Since this is a stateful computation and we know how to translate iteration into recursion, we can cook our own Haskell version of this that uses the State monad to maintain the total and count and uses recursion to iterate over the list:

runningAverages :: [Double] -> [Double]
runningAverages xs = evalState (go xs) (0, 0)
  where
    go []     = return []
    go (x:xs) = do
        (total, count) <- get

        let total'  = total + x
            count'  = count + 1
            average = total' / count'

        put (total', count')

        averages <- go xs
        return $ average : averages

This works as expected:

GHCi

>>> :{
  | runningAverages :: [Double] -> [Double]
  | runningAverages xs = evalState (go xs) (0, 0)
  |   where
  |     go []     = return []
  |     go (x:xs) = do
  |         (total, count) <- get
  |
  |         let total'  = total + x
  |             count'  = count + 1
  |             average = total' / count'
  |
  |         put (total', count')
  |
  |         averages <- go xs
  |         return $ average : averages
  | :}
>>> runningAverages [1,2,3]
[1.0,1.5,2.0]

But it would be a shame if we had to give up the convenience of using map whenever we need a State monad or any monad for that matter. Here's an example that uses the Maybe monad for exception handling. We want to take a list of pairs of numbers and replace each pair (p,q) with the quotient p / q. However, we want to do this safely. If q == 0, we don't want our program to crash. Instead, we use a safe division operator:

safeDiv :: Double -> Double -> Maybe Double
safeDiv _ 0 = Nothing
safeDiv p q = Just $ p / q

If we were to map this function safeDiv over the pairs in a list of numbers, we would get a whole bunch of Maybe Double's:

GHCi

>>> :{
  | safeDiv _ 0 = Nothing
  | safeDiv p q = Just $ p / q
  | :}
>>> map (uncurry safeDiv) [(3,4),(1,2),(3,0),(0,3)]
[Just 0.75,Just 0.5,Nothing,Just 0.0]

Instead of a list of type [Maybe Double], we would like to obtain a result of type Maybe [Double]. If all the divisions of pairs in the list succeeds, the result should be Just the list of quotients. If one or more divisions fail, we want the result to be Nothing. We consider the whole list division to have failed if there exists a pair in the list whose division fails. Here is how we can implement this using the Maybe monad:

listDiv :: [(Double, Double)] -> Maybe [Double]
listDiv [] = return []
listDiv ((p, q):xs) = do
    quot  <- safeDiv p q
    quots <- listDiv xs
    return $ quot : quots

GHCi

>>> :{
  | listDiv :: [(Double, Double)] -> Maybe [Double]
  | listDiv [] = return []
  | listDiv ((p, q):xs) = do
  |     quot  <- safeDiv p q
  |     quots <- listDiv xs
  |     return $ quot : quots
  | :}
>>> listDiv [(3,4),(1,2),(3,0),(0,3)]
Nothing
>>> listDiv [(3,4),(1,2),(0,3)]
Just [0.75,0.5,0.0]

The implementation of listDiv is not quite as awful as that of runningAverages, but it surely isn't as succinct as map (uncurry safeDiv), and it is error-prone to have to cook our own recursive function for something that is still only a simple function application to each list element. The only difference is that the function we're applying isn't a pure function; it's a function that decorates its result using the Maybe monad.

So let's look at mapM, filterM, zipWithM, and foldM, which do exactly the same as map, filter, zipWith, and foldl, only the functions they apply to transform, filter or combine list elements are functions that decorate their results using some monad. These functions are provided by the Control.Monad module of the standard library. I encourage you to use Hoogle to find out what other functions there are. For example, a useful function to know about is mapM_.