# Foldl as foldr

### From HaskellWiki

(Difference between revisions)

(foldl using Update monoid) |
(foldlMaybeMonoid) |
||

Line 51: | Line 51: | ||

By the way: |
By the way: |
||

+ | <hask>Update a</hask> is just <hask>Dual (Endo a)</hask>. |
||

If you use a <hask>State</hask> monad instead of a monoid, |
If you use a <hask>State</hask> monad instead of a monoid, |
||

you obtain an alternative implementation of <hask>mapAccumL</hask>. |
you obtain an alternative implementation of <hask>mapAccumL</hask>. |
||

Line 58: | Line 59: | ||

The answer to the second question is: |
The answer to the second question is: |
||

− | We can write a <hask>foldl</hask> that may stop before reaching the end of the input list |
+ | Using the <hask>foldr</hask> expression we can write variants of <hask>foldl</hask> |

+ | that behave slightly different from the original one. |
||

+ | E.g. we can write a <hask>foldl</hask> that can 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 |
The function <hask>foldlMaybe</hask> terminates with <hask>Nothing</hask> as result |
||

Line 68: | Line 69: | ||

</haskell> |
</haskell> |
||

+ | Maybe the monoidic version is easier to understand. |
||

+ | The implementation of the fold is actually the same, we do only use a different monoid. |
||

+ | <haskell> |
||

+ | import Control.Monad ((>=>), ) |
||

+ | |||

+ | newtype UpdateMaybe a = UpdateMaybe {evalUpdateMaybe :: a -> Maybe a} |
||

+ | |||

+ | instance Monoid (UpdateMaybe a) where |
||

+ | mempty = UpdateMaybe Just |
||

+ | mappend (UpdateMaybe x) (UpdateMaybe y) = UpdateMaybe (x>=>y) |
||

+ | |||

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

+ | foldlMaybeMonoid f a bs = |
||

+ | flip evalUpdateMaybe a $ |
||

+ | mconcat $ |
||

+ | map (UpdateMaybe . flip f) bs |
||

+ | </haskell> |
||

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

## Revision as of 23:12, 16 February 2009

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

that bothfoldl

foldl'

foldr

foldr

foldr

foldl

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?

## 1 Folding by concatenating updates

Instead of thinking in terms offoldr

g

I find it easier to imagine a fold as a sequence of updates. An update is a function mapping from an old value to an updated new value.

newtype Update a = Update {evalUpdate :: a -> a}

We need a way to assemble several updates.

To this end we define aMonoid

instance Monoid (Update a) where mempty = Update id mappend (Update x) (Update y) = Update (y.x)

Now left-folding is straight-forward.

foldlMonoid :: (a -> b -> a) -> a -> [b] -> a foldlMonoid f a bs = flip evalUpdate a $ mconcat $ map (Update . flip f) bs

foldr

mconcat

mconcat :: Monoid a => [a] -> a mconcat = foldr mappend mempty

mappend

Update

mconcat

foldl

foldl

By the way:

Update a

Dual (Endo a)

State

mapAccumL

## 2 foldl which may terminate early

The answer to the second question is:

Using thefoldr

foldl

that behave slightly different from the original one.

E.g. we can write afoldl

and thus may also terminate on infinite input.

The functionfoldlMaybe

Nothing

Nothing

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

Maybe the monoidic version is easier to understand. The implementation of the fold is actually the same, we do only use a different monoid.

import Control.Monad ((>=>), ) newtype UpdateMaybe a = UpdateMaybe {evalUpdateMaybe :: a -> Maybe a} instance Monoid (UpdateMaybe a) where mempty = UpdateMaybe Just mappend (UpdateMaybe x) (UpdateMaybe y) = UpdateMaybe (x>=>y) foldlMaybeMonoid :: (a -> b -> Maybe a) -> a -> [b] -> Maybe a foldlMaybeMonoid f a bs = flip evalUpdateMaybe a $ mconcat $ map (UpdateMaybe . flip f) bs