Foldl as foldr

From HaskellWiki
Revision as of 22:01, 16 February 2009 by Lemming (talk | contribs) (foldlMaybe)

Jump to: navigation, search

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:

  • How can someone find a convolved expression like this?
  • How can we benefit from this rewrite?

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