foldM
Finally, let's look at the effectful sibling of foldl, called foldM. We can
use foldl to add a bunch of numbers:
>>> foldl (+) 0 [1..10]
55
But this doesn't work if the function we use to combine the values in the list returns a value decorated by some monad. In this case, we need
foldM :: Monad m => (b -> a -> m b) -> b -> [a] -> m b
foldM f = go
where
go accum [] = return accum
go accum (x:xs) = do
accum' <- f accum x
go accum' xs
Just as foldl, foldM starts with an initial accumulator value accum. It
then "adds" each list element to this accumulator value using the provided
function f. However, f decorates its return value using some monad m, and
foldM threads the effects of the applications of f to all list elements
through the entire computation.
As a really simple example, consider summing up a list of numbers. Only they
aren't really numbers, they are Maybe numbers. If all entries in the list are
Just numbers, we want the result of summing them up to be Just the sum of
all the numbers in the list:
>>> sumMaybes [Just 3, Just 4, Just 7, Just 0]
Just 14
If there's at least one Nothing in the list, we want the result to be
Nothing.
>>> sumMaybes [Just 3, Just 4, Nothing, Just 0]
Nothing
This function is really easy to implement using foldM, even though it takes
some squinting to see how it works:
sumMaybes :: Num a => [Maybe a] -> Maybe a
sumMaybes = foldM (fmap . (+)) 0
Let's puzzle this apart. Since the monad we use to decorate the result of
sumMaybes is the Maybe monad, the accumulator has type a, and the list
elements are of type Maybe a, we need the function passed to foldM as the
first argument to have the type a -> Maybe a -> Maybe a. If the arguments are
x and Just y, we want the result to be Just (x + y). If the arguments are
x and Nothing, we want the result to be Nothing: The whole fold fails once
we encounter the first Nothing in the list to be folded. By applying (+) to
our accumulator value—let's call it total—we obtain the function (total +),
which has the type a -> a. It returns the result of adding its argument to
total. Applying fmap . (+) to total produces the function fmap (total +),
which has the type Maybe a -> Maybe a. It maps Nothing to Nothing and
Just x to Just (total + x). Thus, if the second argument of fmap . (+) is
Just x, the new accumulator value is total + x. If the second argument is
Nothing, the result is Nothing and the fold fails. This is exactly the
behaviour we want. Try it out:
>>> sumMaybes = foldM (fmap . (+)) 0
>>> sumMaybes [Just 3, Just 4, Just 7, Just 0]
Just 14
>>> sumMaybes [Just 3, Just 4, Nothing, Just 0]
Nothing