Personal tools

Foldl as foldr

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Graham Hutton's tutorial)
Line 126: Line 126:
in evalUpdateMaybe (mconcat $ map m str) 0
in evalUpdateMaybe (mconcat $ map m str) 0
== See also ==
* Graham Hutton: [ A tutorial on the universality and expressiveness of fold]

Revision as of 01:47, 14 March 2009

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

that both
can be expressed as
. (
may lean so far right it came back left again.) The converse is not true, since
may work on infinite lists, which
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?


1 Folding by concatenating updates

Instead of thinking in terms of
and a function
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.

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

We need a way to assemble several updates.

To this end we define a
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
Now, where is the
? It is hidden in
mconcat :: Monoid a => [a] -> a
mconcat = foldr mappend mempty
must be associative (and is actually associative for our
could also be written as
, but this is avoided, precisely
fails on infinite lists.

By the way:

Update a
is just
Dual (Endo a)
. If you use a
monad instead of a monoid, you obtain an alternative implementation of

2 foldl which may terminate early

The answer to the second question is:

Using the
expression we can write variants of

that behave slightly different from the original one.

E.g. we can write a
that can stop before reaching the end of the input list

and thus may also terminate on infinite input.

The function
terminates with
as result when it encounters a
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

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 call
readBounded 1234 $ repeat '1'
which will terminate with
readBounded :: 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