CODEWITHSUNDEEP
haskellrecursionbind
Fale
Fale

Reputation: 147

Haskell: define foldM in do-notation

I am confused about defining foldM in a do-block, mainly because of its recursion. The standard definition for foldM is as follows:

foldM             :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
foldM _ a []      =  return a
foldM f a (x:xs)  =  f a x >>= \fax -> foldM f fax xs

I understand this definition; the result of f a x is passed into a new foldM function recursively, until the list is empty. Here is a definition of foldM in a do-block (copied from my uni course material):

foldM _ z []     = return z
foldM f z (x:xs) = do r <- foldM f z xs
                      f r x

I know that the definition of a do block is basically syntactic sugar for bind (>>=) operations. However, I can't seem to grasp how this definition works. I find recursion in do-blocks overall very confusing. What is given to r? How can the recursive line r <- foldM f z xs be correct when foldM is passed z every recursive call? Shouldn't it be passed a recursively updated argument like f z x, as in the foldM definition with (>>=)?

Upvotes: 3

Views: 968

Answers (1)

Zeta
Zeta

Reputation: 105905

The latter variant evaluates the actions on the list from right-to-left, whereas the other one evaluates the actions on the list from right-to-left. Let's call the latter foldMDo, so that we can keep them apart:

foldM             :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
foldM _ a []      =  return a
foldM f a (x:xs)  =  f a x >>= \fax -> foldM f fax xs

foldMDo _ z []     = return z
foldMDo f z (x:xs) = do r <- foldMDo f z xs
                      f r x

If we use them to print a list, the difference is immediately obvious: 

ghci> foldM (\_ y -> print y) () [1..10]
1
2
3
4
5
6
7
8
9
10

ghci> foldMDo (\_ y -> print y) () [1..10]
10
9
8
7
6
5
4
3
2
1

So, let's desugar the do variant:

do r <- foldMDo f z xs
   f r x

is the same as

foldMDo f z xs >>= \fzxs -> f fzxs x

Let's compare this to the other one next to each other:

(1) f a x          >>= \fax  -> foldM f fax  xs
(2) foldMDo f z xs >>= \fzxs ->       f fzxs x

We can compare that to foldl and foldr with explicit let...in:

foldr f a (x:xs) = let acc = foldr f a xs
                   in f a acc
foldl f a (x:xs) = let acc = f a x
                   in foldr f acc xs

The uni material looks like foldr, whereas the default one looks like foldl, as it is expected with the order of evaluation.

And for completion, let's add the do version of your foldM:

foldM f a (x:xs) = do fax <- f a x
                      foldM f fax xs

TL;DR

Your uni course material doesn't implement foldM, since it doesn't do left-to-right evaluation, but instead right-to-left. Essentially,

Upvotes: 2

Related Questions