Viktor Dukhovni ietf-dane at dukhovni.org
Fri Jan 4 01:57:26 UTC 2019

```On Tue, Jan 01, 2019 at 05:33:39PM +0300, Michail Pevnev wrote:

> Recently I've run into a situation where a monadic fold seems like an
> interesting option. However, I'm not particularly sure how to choose which fold
> - left or right - to use.
>
> Odd things begin when I edit the above to use foldrM. It doesn't terminate on
> an infinite list, which is expected from a disguised foldl. But given several
> negative numbers in the input, it prints out the last one, seemingly turning
> the usual behaviour of Either on its head. It seems its foldl heritage results
> in applying side-effects (in case of Either, erroring out with a Left) in
> reverse order. Do I get this right and is this the general behaviour of foldrM

Short version:  Yes, because expanding the definitions one gets:

foldlM f z0 xs = (\z -> flip f x1 z >>= ... >>= flip f xn) z0
foldrM f z0 xs = (\z ->      f xn z >>= ... >>=      f x1) z0

\$ ghci
λ> import Data.Foldable
λ> let f a b = let s = "("++a++", "++b++")" in putStrLn s >> return s
λ> foldlM f "z" ["a", "b", "c"] >> return ()
(z, a)
((z, a), b)
(((z, a), b), c)
λ> foldrM f "z" ["a", "b", "c"] >> return ()
(c, z)
(b, (c, z))
(a, (b, (c, z)))

Longer version, if we define:

-- Kleisli composition
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
f >=> g = \a -> f a >>= g

-- K is for Kleisli
newtype K m a b = K { runK :: a -> m b }

-- newtype wrapped composition
kcomp :: Monad m => K m a b -> K m b c -> K m a c
(K f) `kcomp` (K g) = K \$ f >=> g

-- K m a a is Monoid under Kleisli composition
instance Monad m => Monoid (K m a a) where
mempty = K return
mappend f g = f `kcomp` g

Expanding the definitions of foldrM, it is not too hard to see that:

foldrM f z0 [] = return z0
foldrM f z0 xs = (\z -> f xn z >>= ... >>= f x1) z0
= (runK (f xn) >=> ... >=> runK (f x1)) z0
= runK (foldMap f' (reverse xs)) z0
where
f' = K . f

Thus foldrM is just a foldMap of some Kleisli compositions of the
(f x_i) in reverse order.  It is right associative, and the
side-effects happen in right-to-left order.  foldrM is strict in
the length of the list.

While on the other hand foldlM is

foldlM f z0 [] = return z0
foldlM f z0 xs = (\z -> flip f x1 z >>= ... >>= flip f x1) z0
= (runK (flip f x1) >=> ... >=> runK (flip f xn)) z0
= runK (foldMap f' xs) z0
where
f' = K . flip f

So foldlM is just a foldMap of some Kleisli compositions  of the
(flip f x_i) in natural order.  foldlM is left associative, and the
side-effects happen in left-to-right order.  If the monad's (>>=)
operator is lazy in its right argument, the computation may
short-circuit after traversing only an initial segment of the
possibly infinite list.

--
Viktor.
```