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.