Difference between revisions of "Foldl as foldr"

From HaskellWiki
Jump to: navigation, search
(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 71:
 
</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 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?


Folding by concatenating updates

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

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 foldr? It is hidden in mconcat.

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

Since mappend must be associative (and is actually associative for our Update monoid), mconcat could also be written as foldl, but this is avoided, precisely foldl fails on infinite lists.

By the way: Update a is just Dual (Endo a). If you use a State monad instead of a monoid, you obtain an alternative implementation of mapAccumL.


foldl which may terminate early

The answer to the second question is: Using the foldr expression we can write variants of foldl that behave slightly different from the original one. E.g. we can write a foldl that can 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

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