Understanding `foldM`

Question

I'm looking at foldM in order to gain intuition as to how it's used.

foldM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a

In this simple example, I simply return [Just 100]. But, what if I want to use the b?

ghci> foldM (\a _ -> return a) (Just 100) [1,2,3] :: [Maybe Int]
[Just 100]

I'm confused how to use the b within (a -> b -> m a).

Please help me gain intuition for this function and how to use the b.

Answer 1

Here's a sort of stupid example. Suppose we wanted to sum the list, and make sure the partial sum never went over (say) 10; thus:

> let ensure p x = x <$ guard (p x)
> foldM (\a b -> ensure (<10) (a+b)) 0 [1,2,3] :: Maybe Integer
Just 6
> foldM (\a b -> ensure (<10) (a+b)) 0 [5,5,5,-10] :: Maybe Integer
Nothing

Answer 2

I believe you have a problem with foldl and not with foldM. foldM is basically just a very minor variation of foldl.

So consider:

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f x xs

What "happens" is: - If xs == [] then x is returned. - otherwise f is called as: f x (xs !! 0) obtaining the result value y :: a. Then f is called as: f y (xs !! 1), obtaining z. Then we go for f z (xs !! 2) etc.

As you can see every call to f is passed the current result up to that point and the next element from the list in input. So it's used whenever you want to reduce a list into a single value and the computation you want to do is "sequential", i.e. you compute a value from the first element, then from this value and the following element you compute the new value, and from this and the second element you compute a new one etc.

For example:

f ys x = map (+x) ys ++ [x]
foldl f [] [1,2,3]

produces:

[6, 5, 3]

Because:

• f [] 1 = [1]
• f [1] 2 = [1+2, 2] = [3, 2]
• f [3, 2] 3 = [3+3, 2+3, 3] = [6, 5, 3]

To better understand how foldl and foldr work, see:

• Haskell- foldl and foldr?
• Writing foldl using foldr
• Implications of foldr vs. foldl (or foldl')
• foldl versus foldr behavior with infinite lists
• http://foldl.com/ and http://foldr.com/
• https://wiki.haskell.org/Fold

Now, foldM is the same as foldl but now the f :: a -> b -> a has type f :: a -> b -> m a. This means that the function that combine the current result with the next element is a monadic action, i.e. it can have effects.

For example, consider:

f ys x = do
    let a = map (+x) ys ++ [x]
    print a
    return a

foldM f [] [1,2,3]

What happens is that the text:

[1]
[3,2]
[6,5,3]

gets printed and the value [6, 5, 3] is the return value of the monadic action.