Foldl as foldr

Revision as of 22:01, 16 February 2009 by Lemming (Talk | contribs)

When you wonder whether to choose foldl or foldr you may remember,

that both

foldl

and

foldl'

can be expressed as

foldr

. (

foldr

may lean so far right it came back left again.) The converse is not true, since

foldr

may work on infinite lists, which

foldl

variants never can do.

It holds

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f a bs =
   foldr (\b g x -> g (f x b)) id bs a

Now the question are:

The answer to the second question is:

We can write a

foldl

that may stop before reaching the end of the input list

and thus may also terminate on infinite input.

The function

foldlMaybe

terminates with

Nothing

as result when it encounters a

Nothing

as interim accumulator result.

foldlMaybe :: (a -> b -> Maybe a) -> a -> [b] -> Maybe a
foldlMaybe f a bs =
   foldr (\b g x -> f x b >>= g) Just bs a