[Haskell-cafe] Left and right monadic folds
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
> 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.
More information about the Haskell-Cafe
mailing list