Difference between revisions of "Foldl as foldr alternative"
m 

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

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

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

−  +  foldl :: (a > x > r) > a > [x] > r 

−  f a 
+  foldl f a list = go a list 
+  where 

+  go a [] = a 

+  go a (x : xs) = go (f a x) xs 

</haskell> 
</haskell> 

−  
−  
−  While we're at it, let's give a name to <hask>foldl f</hask>: <hask>stuff</hask>. So 

−  
−  
−  <haskell> 

−  stuff :: Ord x => Set x > [x] > Set x 

−  stuff a [] = a 

−  stuff a (x:xs) = stuff (f a x) xs 

−  </haskell> 

−  
−  
−  takes all the elements of the list it's given and stuffs them into the <hask>Set</hask> it's given. 

Line 36:  Line 24:  
−  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> 
+  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>—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> 
<haskell> 

−  +  foldl :: (a > x > r) > a > [x] > r 

−  +  foldl f a list = go2 list a 

−  +  where 

+  go2 [] a = a 

+  go2 (x : xs) a = go2 xs (f a x) 

</haskell> 
</haskell> 

−  So now we see that <hask> 
+  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: 
<haskell> 
<haskell> 

−  +  foldl :: (a > x > r) > a > [x] > r 

−  +  foldl f a list = go2 list a 

−  +  where 

+  go2 [] = \a > a 

+  go2 (x : xs) = \a > go2 xs (f a x) 

</haskell> 
</haskell> 

Line 60:  Line 48:  
<haskell> 
<haskell> 

−  stuffy :: Ord x => [x] > Set x > Set x 

⚫  
−  stuffy [] = (\a > a) 

⚫  
−  +  go2 [] = (\a > a) 

+  go2 (x : xs) = \a > (go2 xs) (f a x) 

</haskell> 
</haskell> 

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

−  stuffy :: Ord x => [x] > Set x > Set x 

⚫  
⚫  
where 
where 

whatsit x r = \a > r (f a x) 
whatsit x r = \a > r (f a x) 

Line 81:  Line 68:  
<haskell> 
<haskell> 

−  stuffy :: Ord x => [x] > Set x > Set x 

⚫  
−  stuffy list a = (foldr whatsit (\a > a) list) a 

where 
where 

whatsit x r = \a > r (f a x) 
whatsit x r = \a > r (f a x) 

Line 88:  Line 74:  
−  And that's just about it! We wanted <hask>stuff</hask>, however, not <hask>stuffy</hask>, so let's swap the argument order again: 

⚫  And that's all she wrote! One way to look at this final expression is that <hask>whatsit</hask> 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 <hask>f</hask> to the accumulator it's given and the list element, and passes the result forward to the function it got. 

−  
−  
−  <haskell> 

−  stuff :: Ord x => Set a > [x] > Set x 

⚫  
⚫  
−  whatsit x r = \a > r (f a x) 

−  </haskell> 

−  
−  
−  Now since we do want to be able to use general <hask>foldl</hask> forms, we should generalize it again: 

−  
−  
−  <haskell> 

−  foldl :: (a > x > r) > a > [x] > r 

⚫  
−  where 

−  whosit x r = \a > r (f a x) 

−  </haskell> 

−  
−  
⚫ 
Revision as of 05:42, 4 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 a [] = a
go a (x : xs) = go (f a 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 a xs
as (go a) 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 [] a = a
go2 (x : xs) a = go2 xs (f a 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:
foldl :: (a > x > r) > a > [x] > r
foldl f a list = go2 list a
where
go2 [] = \a > a
go2 (x : xs) = \a > go2 xs (f a 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 [] = (\a > a)
go2 (x : xs) = \a > (go2 xs) (f a 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 (\a > a) ys
where
whatsit x r = \a > r (f a x)
Substituting this in,
foldl f a list = (foldr whatsit (\a > a) list) a
where
whatsit x r = \a > r (f a 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.