Constant space short circuiting `foldM` over `Maybe`

user_525980 0
Viewed 115

Lets say I have the following:

f :: b -> a -> b
x :: b
l :: [a]

and

foldl' f x l

runs in constant space. That is f is suitably strict.

Now consider if I have:

f2 :: b -> a -> Maybe b
f2 x y = if (pred x y) then Just $! (f x y) else Nothing

will

foldM f2 x l

reliably run in constant space? Or is there something else I need to do to ensure I have both constant space but still the short circuiting behaviour of Maybe?

(Note whilst I've asked this question about Maybe, I actually want to do this with Either, but I suspect the approach is similar)

haskell
1 Answers

In the library source code foldM is defined as foldlM, which in turn is defined as

foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldr c return xs z0
  where c x k z = f z x >>= k

Assuming, c x k z = f2 z x >>= k, let's see what happens when we call it. To see if it's constant space or not, we will only reduce the expressions by applying the topmost function without reducing the subexpressions.

foldlM f2 z0 (x:xs)
=
foldr c return (x:xs) z0
=
c x (foldr c return xs) z0
=
f2 z0 x >>= foldr c return xs

Since >>= is strict on the first arg, we evaluate f2 z0 x first. If that returns Nothing, we ignore the rest (short-circuiting, as you mentioned). If that returns Just y, we have

Just y >>= foldr c return xs
=
foldr c return xs y

and we are ready for the next loop.

This did not cause our term to grow, so it looks like it runs in constant space (provided f2 keeps the size of y constant, of course).

user_32349590
Related