Personal tools

Foldl as foldr alternative

From HaskellWiki

Jump to: navigation, search
This page explains how
foldl
can be written using
foldr
. Yes, there is already such a page! This one explains it differently.


The usual definition of
foldl
looks like this:


foldl :: (a -> x -> r) -> a -> [x] -> r
foldl f a [] = a
foldl f a (x : xs) = foldl f (f a x) xs


Now the
f
never changes in the recursion. It turns out things will be simpler later if we pull it out:


foldl :: (a -> x -> r) -> a -> [x] -> r
foldl f a list = go a list
  where
    go acc [] = acc
    go acc (x : xs) = go (f acc x) xs




For some reason (maybe we're crazy; maybe we want to do weird things with fusion; who knows?) we want to write this using
foldr
. Haskell programmers like curry, so it's natural to see
go acc xs
as
(go acc) xs
—that is, to see
go a
as a function that takes a list and returns the result of folding
f
into the list starting with an accumulator value of
a
. This perspective, however, is the wrong one for what we're trying to do here. So let's change the order of the arguments of the helper:


foldl :: (a -> x -> r) -> a -> [x] -> r
foldl f a list = go2 list a
  where
    go2 [] acc = acc
    go2 (x : xs) acc = go2 xs (f acc x)


So now we see that
go2 xs
is a function that takes an accumulator and uses it as the initial value to fold
f
into
xs
. With this shift of perspective, we can rewrite
go2
just a little, shifting its second argument into an explicit lambda:


foldl :: (a -> x -> r) -> a -> [x] -> r
foldl f a list = go2 list a
  where
    go2 [] = \acc -> acc
    go2 (x : xs) = \acc -> go2 xs (f acc x)


Believe it or not, we're almost done! How is that? Let's parenthesize a bit for emphasis:


foldl f a list = go2 list a
  where
    go2 [] = (\acc -> acc)                      -- nil case
    go2 (x : xs) = \acc -> (go2 xs) (f acc x)   -- construct x (go2 xs)


This isn't an academic paper, so we won't mention Graham Hutton's "Tutorial on the Universality and Expressiveness of Fold", but
go2
fits the
foldr
pattern, constructing its result in non-nil case from the list's head element (
x
) and the recursive result for its tail (
go2 xs
):


go2 list = foldr construct (\acc -> acc) list
  where
    construct x r = \acc -> r (f acc x)


Substituting this in,


foldl f a list = (foldr construct (\acc -> acc) list) a
  where
    construct x r = \acc -> r (f acc x)


And that's all she wrote! One way to look at this final expression is that
construct
takes an element
x
of the list, a function
r
produced by folding over the rest of the list, and the value of an accumulator,
acc
, "from the left". It applies
f
to the accumulator and the list element, and passes the result forward to the function it got "on the right".


Because
r
is the same function as constructed by the
construct
here, calling this e.g. for a list
[x,y,...,z]
scans through the whole list as-if evaluating a nested lambda applied to the initial value of the accumulator,


(\acc-> 
    (\acc-> 
        (... (\acc-> (\acc -> acc)
                      (f acc z)) ...)
        (f acc y))
    (f acc x)) a

which creates the chain of evaluations as in

(\acc -> acc) (f (... (f (f a x) y) ...) z)


which is just what the normal
foldl
would do.




The
construct
function could even be made more clever, and inspect the current element in order to decide whether to process the list further or not. Thus, such a variant of
foldl
will be able to stop early, and thus process even infinite lists:


foldlWhile t f a list = foldr cons (\acc -> acc) list a
  where
    cons x r = \acc -> if t x then r (f acc x) else acc


And if we want our
foldl
to decide whether to process or skip the current element, then it's


foldlIf t f a list = foldr cons (\acc -> acc) list a
  where
    cons x r = \acc -> if t x then r (f acc x) else r acc


(Just for comparison, skipping
foldr
is of course, trivial:)


foldrIf t f a list = foldr cons a list
  where
    cons x r | t x = f x r 
             | otherwise = r

Another variation is (a more strict and more general)

foldl'Breaking break reduced reducer acc list = 
    foldr cons (\acc -> acc) list acc 
          where 
          cons x r acc | break acc x = reduced acc x 
                       | otherwise   = r $! reducer acc x