A simple example of `foldM`
Looking at foldM
:
foldM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a
I tried to create an example foldM
that just added each list item to it [1,2,3]
.
Based on my initial (wrong) understanding foldM
, I expected the [[1], [2], [3]]
following as a result:
ghci> let f = (\xs x -> [x] : [xs])
But I was wrong:
ghci> foldM f [] [1,2,3]
[[3],[2],[3],[1],[3],[2],[3],[]]
Please explain what is happening in this example.
source to share
After reading the documentation and setting up with help foldM
in GHCi, I think I can explain what happened in your example. Let's revisit the type signature foldM
:
foldM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a
From this type signature, you can deduce that it foldM
takes a function (a -> b -> m a)
and applies it to each element of the list ( [b]
). The second parameter is the initial value passed to the function in the "first call". Subsequent calls use the resulting value of the function ("fetched" from m a
).
Thus, when you do:
ghci> let f = (\xs x -> [x] : [xs])
ghci> foldM f [] [1,2,3]
[[3],[2],[3],[1],[3],[2],[3],[]]
This is equivalent to:
ghci> ([] `f` 1) >>= (`f` 2) >>= (`f` 3)
ghci> [[3],[2],[3],[1],[3],[2],[3],[]]
If we break the line above into the following subexpressions, we can more clearly see what's going on:
ghci> ([] `f` 1)
ghci> [[1],[]]
ghci> ([] `f` 1) >>= (`f` 2)
ghci> [[2],[1],[2],[]]
...
The function f
takes a list and a value as arguments, creates a singleton list (putting the value in its own list), and adds it to the list of lists. Initially, when we have an empty list, the result is obvious: [[1],[]]
(which is ours "m a"
in the type signature). Now, as I said, to call f
again, you need to take a new value "a"
from this result. This time, we call to f
pass the retrieved value and the next value in the attached list (i.e. 2
from [1,2,3]
). The question that we "m a"
have [[1],[]]
a list of which we need to pass as the first argument f
: [1]
or []
? And the answer depends on the behavior of the operator>>=
for lists, which can be thought of as a non-deterministic computation, which applies the given function to each item in the given list and concatenates the results. For this particular step, the example f
will call twice for two different first parameters: f [1] 2
and f [] 2
.
I tried to answer a question based on the example provided by the author, but the monadic chaining used to define the behavior foldM
in this particular case can be used to reason about any Monad.
source to share