View source for Foldl as foldr alternative

This page explains how <hask>foldl</hask> can be written using <hask>foldr</hask>. Yes, there is already [[Foldl as foldr|such a page]]! This one explains it differently.


The usual definition of <hask>foldl</hask> looks like this:


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


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


<haskell>
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
</haskell>


-----


For some reason (maybe we're crazy; maybe we want to do weird things with fusion; who knows?) we want to write this using <hask>foldr</hask>. Haskell programmers like curry, so it's natural to see <hask>go acc xs</hask> as <hask>(go acc) xs</hask>&mdash;that is, to see <hask>go a</hask> as a function that takes a list and returns the result of folding <hask>f</hask> into the list starting with an accumulator value of <hask>a</hask>. 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:


<haskell>
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)
</haskell>


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


<haskell>
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)
</haskell>


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


<haskell>
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)
</haskell>


This isn't an academic paper, so we won't mention Graham Hutton's [https://www.cs.nott.ac.uk/~gmh/fold.pdf "Tutorial on the Universality and Expressiveness of Fold"], but <hask>go2</hask> fits the <hask>foldr</hask> pattern, constructing its result in non-nil case from the list's head element (<hask>x</hask>) and the recursive result for its tail (<hask>go2 xs</hask>):


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


Substituting this in,


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


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


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


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

which creates the chain of evaluations as in 

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


which is just what the normal <hask>foldl</hask> would do.


----


The <hask>construct</hask> 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 <hask>foldl</hask> will be able to stop early, and thus process even infinite lists:


<haskell>
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
</haskell>


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


<haskell>
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
</haskell>


(Just for comparison, skipping <hask>foldr</hask> is of course, trivial:)


<haskell>
foldrIf t f a list = foldr cons a list
  where
    cons x r | t x = f x r 
             | otherwise = r
</haskell>

Another variation is (a more strict and more general) 

<haskell>
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
</haskell>