mapM

The first function we have is¹

mapM :: Monad m => (a -> m b) -> [a] -> m [b]
mapM f = go
  where
    go []     = return []
    go (x:xs) = do
        y  <- f  x
        ys <- go xs
        return $ y : ys

Just as map, it applies the function f to every list element and collects the results. However, it also threads whatever decoration the monad provides through the computation. For example, if the monad is Maybe, then the function f has the type a -> Maybe b, that is, it may fail to produce a result for some list elements. Given a list x:xs, go (x:xs) first applies f to the first list element and then recurses on the rest of the list. If f or the recursive call go xs fails to produce a result, then due to the behaviour of the Maybe monad, go (x:xs) also fails to produce a result. This is exactly the behaviour we wanted for listDiv, and we can implement listDiv much more conveniently using mapM:

listDiv :: [(Double, Double)] -> Maybe [Double]
listDiv = mapM (uncurry safeDiv)

GHCi

>>> listDiv = mapM (uncurry safeDiv)
>>> listDiv [(3,4),(1,2),(0,3)]
Just [0.75,0.5,0.0]
>>> listDiv [(3,4),(1,2),(3,0),(0,3)]
Nothing

Similarly, we can re-implement runningAverages, which uses the State monad using mapM:

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

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

        put (total', count')

        return $ total' / count'

Compare this to our Python implementation:

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

If we ignore the fact that we cannot simply overwrite total and count in our Haskell code, our average function looks remarkably similar to an iteration of the Python implementation. First we read the current total and count. We calculate their new values and call them total' and count'. Then we make total' and count' the new total and count using put (total', count'). Finally, we return the current average total' / count', to be collected by mapM and added to the list of averages.

I must emphasize that this implementation of runningAverages was only meant to demonstrate the use of mapM combined with the State monad. The experienced Haskell programmer will implement runningAverages using only pure functions, and much more succinctly:

runningAverages :: [Double] -> [Double]
runningAverages xs = zipWith (/) (tail $ scanl (+) 0 xs) [1..]

GHCi

>>> runningAverages xs = zipWith (/) (tail $ scanl (+) 0 xs) [1..]
>>> runningAverages [1,2,3]
[1.0,1.5,2.0]

scanl is a function that is closely related to foldl. Both foldl f init xs and scanl f init xs "add" each list element in xs to the accumulator initialized to init, and they use the function f to implement this "addition", to compute the new accumulator value from the old one and the current list element. The difference is that foldl reports only the final accumulator value, while scanl reports a list containing the initial accumulator value and the accumulator values obtained after adding each list element:

GHCi

>>> scanl (+) 0 [1..10]
[0,1,3,6,10,15,21,28,36,45,55]

The implementation of scanl is fairly straightforward:

scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanl f = go
  where
    go accum []     = [accum]
    go accum (x:xs) = accum : go (f accum x) xs

Compare this to the implementation of foldl:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f = go
  where
    go accum []     = accum
    go accum (x:xs) = go (f accum x) xs

Really similar.

I mentioned that every monad is an applicative functor and then avoided talking about applicative functors in order not to throw yet another abstraction into the mix. However, I cannot quite resist pointing out that using the fact that every monad is an applicative functor, we have a much shorter implementation of mapM:
```
mapM :: Monad m => (a -> m b) -> [a] -> m [b]
mapM f = go
  where
    go []     = return []
    go (x:xs) = (:) <$> f x <*> go xs
```
↩