[Haskell-cafe] Left and right monadic folds

[Michail Pevnev]

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.