# Difference between revisions of "Foldl as foldr alternative"

Line 19: | Line 19: | ||

foldl f a list = go a list |
foldl f a list = go a list |
||

where |
where |
||

− | go |
+ | go acc [] = acc |

− | go |
+ | 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 |
+ | 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>—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 [] |
+ | go2 [] acc = acc |

− | go2 (x : xs) |
+ | 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 [] = \ |
+ | go2 [] = \acc -> acc |

− | go2 (x : xs) = \ |
+ | 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 [] = (\ |
+ | go2 [] = (\acc -> acc) |

− | go2 (x : xs) = \ |
+ | go2 (x : xs) = \acc -> (go2 xs) (f acc x) |

</haskell> |
</haskell> |
||

Line 66: | Line 66: | ||

<haskell> |
<haskell> |
||

− | go2 ys = foldr whatsit (\ |
+ | go2 ys = foldr whatsit (\acc -> acc) ys |

where |
where |
||

− | whatsit x r = \ |
+ | whatsit x r = \acc -> r (f acc x) |

</haskell> |
</haskell> |
||

Line 76: | Line 76: | ||

<haskell> |
<haskell> |
||

− | foldl f a list = (foldr whatsit (\ |
+ | foldl f a list = (foldr whatsit (\acc -> acc) list) a |

where |
where |
||

− | whatsit x r = \ |
+ | 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.