# Foldl as foldr

### From HaskellWiki

(Difference between revisions)

(foldlMaybe) |
(foldl using Update monoid) |
||

Line 14: | Line 14: | ||

* How can someone find a convolved expression like this? | * How can someone find a convolved expression like this? | ||

* How can we benefit from this rewrite? | * How can we benefit from this rewrite? | ||

+ | |||

+ | |||

+ | == Folding by concatenating updates == | ||

+ | |||

+ | Instead of thinking in terms of <hask>foldr</hask> and a function <hask>g</hask> as argument to the accumulator function, | ||

+ | 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. | ||

+ | <haskell> | ||

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

+ | </haskell> | ||

+ | We need a way to assemble several updates. | ||

+ | To this end we define a <hask>Monoid</hask> instance. | ||

+ | <haskell> | ||

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

+ | mempty = Update id | ||

+ | mappend (Update x) (Update y) = Update (y.x) | ||

+ | </haskell> | ||

+ | Now left-folding is straight-forward. | ||

+ | <haskell> | ||

+ | foldlMonoid :: (a -> b -> a) -> a -> [b] -> a | ||

+ | foldlMonoid f a bs = | ||

+ | flip evalUpdate a $ | ||

+ | mconcat $ | ||

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

+ | </haskell> | ||

+ | Now, where is the <hask>foldr</hask>? | ||

+ | It is hidden in <hask>mconcat</hask>. | ||

+ | <haskell> | ||

+ | mconcat :: Monoid a => [a] -> a | ||

+ | mconcat = foldr mappend mempty | ||

+ | </haskell> | ||

+ | Since <hask>mappend</hask> must be associative | ||

+ | (and is actually associative for our <hask>Update</hask> monoid), | ||

+ | <hask>mconcat</hask> could also be written as <hask>foldl</hask>, | ||

+ | but this is avoided, precisely <hask>foldl</hask> fails on infinite lists. | ||

+ | |||

+ | By the way: | ||

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

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

+ | |||

+ | |||

+ | == foldl which may terminate early == | ||

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

## Revision as of 23:04, 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:

If you use aState

mapAccumL

## 2 foldl which may terminate early

The answer to the second question is:

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