Left and right monadic folds

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Left and right monadic folds

mpevnev
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.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: 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.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.