CODEWITHSUNDEEP
haskell
Kevin Meredith
Kevin Meredith

Reputation: 41909

Understanding `foldM`

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.

Upvotes: 10

Views: 5755

Answers (4)

Daniel Wagner
Daniel Wagner

Reputation: 152682

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

Upvotes: 16

Bakuriu
Bakuriu

Reputation: 101909

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:

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.

Upvotes: 6

Christopher King
Christopher King

Reputation: 10941

Just like with all folds with initializes, the b type variable signifies that you may have a different type of thing for accumulator and the rest. For example, let's say I was repeating a string. I could do

Prelude> import Control.Monad
Prelude Control.Monad> foldM (\str n -> (putStrLn $ "Repeating string " ++ (show str) ++ " " ++ (show n) ++ " times") >> (return $ concat $ replicate n str)) "Yolo" [4,5,6]
Repeating string "Yolo" 4 times
Repeating string "YoloYoloYoloYolo" 5 times
Repeating string "YoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYolo" 6 times
"YoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYoloYolo"

As you can see the type of "Yolo" differs from the types of 4, 5, and 6. This is the same as all folds, foldM just adds a monadic aspect.

Upvotes: 3

Raghu Kaippully
Raghu Kaippully

Reputation: 78

Notice that a and b can be different types. So the function can do anything with the two values as long as it can return a value of type m a.

See the example below. This function is trying to sum up the length of all strings as long as they are not empty. If it finds any empty string, it returns Nothing.

count :: Int -> String -> Maybe Int
count c s = if null s
            then Nothing
            else Just $ c + length s

Now you can try it out:

*Main> foldM count 0 ["Hello", "World"]
Just 10
*Main> foldM count 0 ["Hello", "", "World"]
Nothing

Upvotes: 3

Related Questions