Difference between revisions of "Foldl as foldr"
Jump to navigation
Jump to search
(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