[Haskell-cafe] Left and right monadic folds

[Viktor Dukhovni]

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
> for any monad?

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.