# Difference between revisions of "Foldl as foldr"

From HaskellWiki

(introduction) |
(foldlMaybe) |
||

Line 18: | Line 18: | ||

We can write a <hask>foldl</hask> that may stop before reaching the end of the input list |
We can write a <hask>foldl</hask> that may stop before reaching the end of the input list |
||

and thus may also terminate on infinite input. |
and thus may also terminate on infinite input. |
||

+ | The function <hask>foldlMaybe</hask> terminates with <hask>Nothing</hask> as result |
||

+ | when it encounters a <hask>Nothing</hask> as interim accumulator result. |
||

+ | <haskell> |
||

+ | foldlMaybe :: (a -> b -> Maybe a) -> a -> [b] -> Maybe a |
||

+ | foldlMaybe f a bs = |
||

+ | foldr (\b g x -> f x b >>= g) Just bs a |
||

+ | </haskell> |
||

+ | |||

[[Category:Idioms]] |
[[Category:Idioms]] |

## Revision as of 22:01, 16 February 2009

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
```