Difference between revisions of "Foldl as foldr alternative"

From HaskellWiki
Jump to: navigation, search
Line 19: Line 19:
 
foldl f a list = go a list
 
foldl f a list = go a list
 
where
 
where
go a [] = a
+
go acc [] = acc
go a (x : xs) = go (f a x) xs
+
go acc (x : xs) = go (f acc x) xs
 
</haskell>
 
</haskell>
   
Line 27: Line 27:
   
   
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 a xs</hask> as <hask>(go a) 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:
+
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:
   
   
Line 34: Line 34:
 
foldl f a list = go2 list a
 
foldl f a list = go2 list a
 
where
 
where
go2 [] a = a
+
go2 [] acc = acc
go2 (x : xs) a = go2 xs (f a x)
+
go2 (x : xs) acc = go2 xs (f acc x)
 
</haskell>
 
</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:
+
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:
   
   
Line 46: Line 46:
 
foldl f a list = go2 list a
 
foldl f a list = go2 list a
 
where
 
where
go2 [] = \a -> a
+
go2 [] = \acc -> acc
go2 (x : xs) = \a -> go2 xs (f a x)
+
go2 (x : xs) = \acc -> go2 xs (f acc x)
 
</haskell>
 
</haskell>
   
Line 57: Line 57:
 
foldl f a list = go2 list a
 
foldl f a list = go2 list a
 
where
 
where
go2 [] = (\a -> a)
+
go2 [] = (\acc -> acc)
go2 (x : xs) = \a -> (go2 xs) (f a x)
+
go2 (x : xs) = \acc -> (go2 xs) (f acc x)
 
</haskell>
 
</haskell>
   
Line 66: Line 66:
   
 
<haskell>
 
<haskell>
go2 ys = foldr whatsit (\a -> a) ys
+
go2 ys = foldr whatsit (\acc -> acc) ys
 
where
 
where
whatsit x r = \a -> r (f a x)
+
whatsit x r = \acc -> r (f acc x)
 
</haskell>
 
</haskell>
   
Line 76: Line 76:
   
 
<haskell>
 
<haskell>
foldl f a list = (foldr whatsit (\a -> a) list) a
+
foldl f a list = (foldr whatsit (\acc -> acc) list) a
 
where
 
where
whatsit x r = \a -> r (f a x)
+
whatsit x r = \acc -> r (f acc x)
 
</haskell>
 
</haskell>
   

Revision as of 00:39, 15 September 2014

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)
    go2 (x : xs) = \acc -> (go2 xs) (f acc x)


This isn't an academic paper, so we won't mention Graham Hutton's "Tuturial on the Universality and Expressiveness of Fold", but go2 fits the foldr pattern:


go2 ys = foldr whatsit (\acc -> acc) ys
  where
    whatsit x r = \acc -> r (f acc x)


Substituting this in,


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


And that's all she wrote! One way to look at this final expression is that whatsit takes an element of the list, a function produced by folding over the rest of the list, and the value of an accumulator. It applies f to the accumulator it's given and the list element, and passes the result forward to the function it got.