Difference between revisions of "Foldl as foldr alternative"
(Created page with "This page explains how <hask>foldl</hask> can be written using <hask>foldr</hask>. Yes, there is already such a page! This one explains it differently. The...") |
|||
Line 9: | Line 9: | ||
</haskell> |
</haskell> |
||
− | Now the <hask>f</hask> never changes in the recursion |
+ | Now the <hask>f</hask> never changes in the recursion, so we don't really have to worry too much about it. For simplicity, then, let's pick one in particular: |
<haskell> |
<haskell> |
||
− | + | f :: Ord x => Set x -> x -> Set x |
|
− | + | f a x = insert x a |
|
⚫ | |||
⚫ | |||
⚫ | |||
</haskell> |
</haskell> |
||
+ | While we're at it, let's give a name to <hask>foldl f</hask>: <hask>stuff</hask>. So |
||
⚫ | 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> |
||
<haskell> |
<haskell> |
||
− | + | stuff :: Ord x => Set x -> [x] -> Set x |
|
− | + | stuff a [] = a |
|
⚫ | |||
⚫ | |||
− | go2 [] a = a |
||
⚫ | |||
</haskell> |
</haskell> |
||
+ | takes all the elements of the list it's given and stuffs them into the <hask>Set</hask> it's given. |
||
⚫ | |||
+ | |||
⚫ | 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>stuff a xs</hask> as <hask>(stuff a) xs</hask>—that is, to see <hask>stuff 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 <hask>stuff</hask>. |
||
<haskell> |
<haskell> |
||
− | + | stuffy :: Ord x => [x] -> Set x -> Set x |
|
− | + | stuffy [] a = a |
|
⚫ | |||
− | where |
||
+ | </haskell> |
||
⚫ | |||
+ | |||
⚫ | |||
⚫ | |||
+ | |||
+ | <haskell> |
||
+ | stuffy :: Ord x => [x] -> Set x -> Set x |
||
⚫ | |||
⚫ | |||
</haskell> |
</haskell> |
||
Line 42: | Line 45: | ||
<haskell> |
<haskell> |
||
+ | stuffy :: Ord x => [x] -> Set x -> Set x |
||
⚫ | |||
⚫ | |||
− | where |
||
− | + | stuffy (x : xs) = \a -> (stuffy 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>stuffy</hask> fits the <hask>foldr</hask> pattern: |
<haskell> |
<haskell> |
||
− | + | stuffy :: Ord x => [x] -> Set x -> Set x |
|
+ | stuffy ys = foldr whatsit (\a -> a) ys |
||
where |
where |
||
whatsit x r = \a -> r (f a x) |
whatsit x r = \a -> r (f a x) |
||
Line 59: | Line 62: | ||
<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) |
||
</haskell> |
</haskell> |
||
+ | And that's just about it! We wanted <hask>stuff</hask>, however, not <hask>stuffy</hask>, so let's swap the argument order again: |
||
⚫ | |||
+ | |||
+ | <haskell> |
||
+ | stuff :: Ord x => Set a -> [x] -> Set x |
||
+ | stuff a list = (foldr whatsit (\a -> a) list) a |
||
⚫ | |||
+ | 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 gneralize it again: |
||
+ | |||
+ | <haskell> |
||
+ | foldl :: (a -> x -> r) -> a -> [x] -> r |
||
⚫ | |||
⚫ | |||
⚫ | |||
+ | </haskell. |
||
+ | |||
⚫ | The way to look at this final expression is that <hask>whosit</hask> takes an element of the list, a function produced by folding <hask>f</hask> into the rest of the list, and the initial value, <hask>a</hask> 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. |
Revision as of 05:00, 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, so we don't really have to worry too much about it. For simplicity, then, let's pick one in particular:
f :: Ord x => Set x -> x -> Set x
f a x = insert x a
While we're at it, let's give a name to foldl f
: stuff
. So
stuff :: Ord x => Set x -> [x] -> Set x
stuff a [] = a
stuff a (x:xs) = stuff (f a x) xs
takes all the elements of the list it's given and stuffs them into the Set
it's given.
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 stuff a xs
as (stuff a) xs
—that is, to see stuff 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 stuff
.
stuffy :: Ord x => [x] -> Set x -> Set x
stuffy [] a = a
stuffy (x : xs) a = stuffy xs (f a x)
So now we see that stuffy 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 stuffy
just a little:
stuffy :: Ord x => [x] -> Set x -> Set x
stuffy a [] = \a -> a
stuffy (x : xs) = \a -> stuffy xs (f a x)
Believe it or not, we're almost done! How is that? Let's parenthesize a bit for emphasis:
stuffy :: Ord x => [x] -> Set x -> Set x
stuffy [] = (\a -> a)
stuffy (x : xs) = \a -> (stuffy 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 stuffy
fits the foldr
pattern:
stuffy :: Ord x => [x] -> Set x -> Set x
stuffy ys = foldr whatsit (\a -> a) ys
where
whatsit x r = \a -> r (f a x)
Substituting this in,
stuffy :: Ord x => [x] -> Set x -> Set x
stuffy list a = (foldr whatsit (\a -> a) list) a
where
whatsit x r = \a -> r (f a x)
And that's just about it! We wanted stuff
, however, not stuffy
, so let's swap the argument order again:
stuff :: Ord x => Set a -> [x] -> Set x
stuff a list = (foldr whatsit (\a -> a) list) a
where
whatsit x r = \a -> r (f a x)
Now since we do want to be able to use general foldl
forms, we should gneralize it again:
<haskell> foldl :: (a -> x -> r) -> a -> [x] -> r foldl f a xs = (foldr whosit (\a -> a) list) a
where whosit x r = \a -> r (f a x)
</haskell.
The way to look at this final expression is that whosit
takes an element of the list, a function produced by folding f
into the rest of the list, and the initial value, a
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.