# Foldl as foldr

### From HaskellWiki

m |
|||

Line 11: | Line 11: | ||

(The converse is not true, since <hask>foldr</hask> may work on infinite lists, | (The converse is not true, since <hask>foldr</hask> may work on infinite lists, | ||

− | which <hask>foldl</hask> variants never can do. However, for ''finite'' lists, <hask>foldr</hask> ''can'' be written in terms of <hask>foldl</hask> (although losing laziness in the process), in a similar way like this: | + | which <hask>foldl</hask> variants never can do. However, for ''finite'' lists, <hask>foldr</hask> ''can'' also be written in terms of <hask>foldl</hask> (although losing laziness in the process), in a similar way like this: |

<haskell> | <haskell> | ||

foldr :: (b -> a -> a) -> a -> [b] -> a | foldr :: (b -> a -> a) -> a -> [b] -> a |

## Revision as of 08:55, 21 July 2011

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

that bothIt holds

foldl :: (a -> b -> a) -> a -> [b] -> a foldl f a bs = foldr (\b g x -> g (f x b)) id bs a

*finite*lists,

*can*also be written in terms of

foldr :: (b -> a -> a) -> a -> [b] -> a foldr f a bs = foldl (\g b x -> g (f b x)) id bs a

)

Now the question are:

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

## Contents |

## 1 Folding by concatenating updates

Instead of thinking in terms ofI 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 ainstance 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

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

By the way:

## 2 foldl which may terminate early

The answer to the second question is:

Using thethat behave slightly different from the original one.

E.g. we can write aand thus may also terminate on infinite input.

The functionfoldlMaybe :: (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

## 3 Practical example: Parsing numbers using a bound

As a practical example consider a function that converts an integer string to an integer, but that aborts when the number exceeds a given bound.

With this bound it is possible to callreadBounded :: Integer -> String -> Maybe Integer readBounded bound str = case str of "" -> Nothing "0" -> Just 0 _ -> foldr (\digit addLeastSig mostSig -> let n = mostSig*10 + toInteger (Char.digitToInt digit) in guard (Char.isDigit digit) >> guard (not (mostSig==0 && digit=='0')) >> guard (n <= bound) >> addLeastSig n) Just str 0 readBoundedMonoid :: Integer -> String -> Maybe Integer readBoundedMonoid bound str = case str of "" -> Nothing "0" -> Just 0 _ -> let m digit = UpdateMaybe $ \mostSig -> let n = mostSig*10 + toInteger (Char.digitToInt digit) in guard (Char.isDigit digit) >> guard (not (mostSig==0 && digit=='0')) >> guard (n <= bound) >> Just n in evalUpdateMaybe (mconcat $ map m str) 0

## 4 See also

- Graham Hutton: A tutorial on the universality and expressiveness of fold