Hello everyone. 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. For non-monadic folds the rule of thumb is 'avoid foldl, use foldr for infinite things and foldl' for performance'. What are the guidelines for the monadic ones? The fact that 'foldlM' is implemented (in base-4.12.0-0) using 'foldr' and 'foldrM' uses 'foldl' (also, non-strict foldl, which is worrying) adds somewhat to my confusion. I've played a bit with folding Eithers, and foldlM seems to work somewhat intuitively (breaks on the first Left, as is usual for Either), and also accepts infinite lists (which makes sense, given it's a foldr): import Data.Foldable main :: IO () main = do print $ sumNonNegative $ [1, 2, -4] ++ [5..] sumNonNegative :: [Int] -> Either String Int sumNonNegative = foldlM foo 0 foo :: Int -> Int -> Either String Int foo acc x | x >= 0 = Right $ x + acc | otherwise = Left $ "Negative number: " ++ show x This prints out "Negative number: -4". 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? -- Michail.
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.
participants (2)
-
Michail Pevnev -
Viktor Dukhovni