# Folding

February 12, 2018

Let's continue our exploration of `List` to look at folding.

We got a taste of how lists are different than arrays yesterday when we tried to access the nth element. With lists we have to dig in to nested lists and ask for the appropriate `tail`. Folding is an abstraction of the `reduce` we find in Swift and other languages - the difference is that because of the way in which lists are designed, the behavior and performance differs if we fold from the left or from the right.

So here's what I mean by folding from the left.

Suppose we have the list `fiveSixSeven`. Remember that looks roughly like this.

*
(5(6(7( ))))
*

We can add all the elements together with a left fold. We just need to specify a starting value for our accumulator: `0`, and we have to specify a rule that takes our accumulator and the next element from the list and produces the next value of the accumulator. In this case, it's just `+`. You could instead write it as a closure using something more like this:

*
{(accumulator, element) in accumulator + element}
*

So how would the left fold work?

If we call the left fold on the empty list we get the current value of the accumulator.

Otherwise, we apply the rule to the current value of the accumulator and the next element of the list and then recursively call the left fold on the `tail` of the list.

Here's what the code might look like.

*
extension List {
func foldLeft<B>(_ initialValue: B, _ f: @escaping(B, A) -> B) -> B {
guard case let .cons(head, tail) = self else {return initialValue}
return tail.foldLeft(f(initialValue, head), f)
}
}
*

`foldLeft` is generic in `B` because we are free to create a rule and initial value that produce an accumulator of any type.

One more side comment, I initially implemented `foldLeft` using `switch`, like this.

*
**// I prefer the other implementation*
func foldLeft<B>(_ initialValue: B, _ f: @escaping(B, A) -> B) -> B {
switch self {
case .empty:
return initialValue
case .cons(let head, let tail):
return tail.foldLeft(f(initialValue, head), f)
}
}

I like the concision of `guard case` (a variant of `if case`).

Here's today's sample code and here's the Playground it comes from so you can follow along or pause now and then to work ahead.

We can use `foldLeft` in a point free style like this.

*
fiveSixSeven.foldLeft(0, +)
*

Or we could use a trailing closure, like this.

*
fiveSixSeven.foldLeft(0){(accumulator, element) in
accumulator + element
}
*

In either case, the result is `18`.

OK. No big deal.

What happens if our rule is meant to transform our list. Say we want to just add 1 to each element in the list.

First, we need a method that appends an element to a list. Our strategy is simple. We create a new `List.cons` and our current list becomes the `tail` and the new element is the `head`. In other words, we add to the beginning of the list like this using `append`.

*
extension List {
var head: A {
guard case .cons(let head, _) = self else {
fatalError("The list is empty.")
}
return head
}
var tail: List {
guard case .cons(_, let tail) = self else {
fatalError("The list is empty.")
}
return tail
}
func element(number n: Int) -> A {
guard n > 0 else {return head}
return tail.element(number: n - 1)
}
func append(_ element: A) -> List {
return List.cons(head: element, tail: self)
}
}
*

So here's how we can use `foldLeft` and `append` to add one to each element of the list.

*
fiveSixSeven.foldLeft(emptyList){(accumulator, element)
in accumulator.append(element + 1)
}
*

The result is `(8(7(6( ))))`.

That's not exactly what we want to see. We would have liked the order to stay the same. We want `(6(7(8( ))))`.

Now here's the exercise books always suggest at this point and I always skipped until recently.

Trace through what happens when you perform the `foldLeft` in each of the two examples step-by-step.

Do you see why the order is reversed?

The advantage of the left fold is we could use tail recursion and there is an efficiency in space that we won't get when we implement a right fold in a moment.

A left fold is folding up the list from the left to the right. First the `5` is consumed, then the `6`, then the `7`.

To contrast, a right fold folds up the list from the right. We dig all the way in to the innermost element and start by consuming the `7`, then the `6`, then the `5`. There is a lot of deferred calculation going on.

Here's one implementation of `foldRight`.

*
extension List {
func foldLeft<B>(_ initialValue: B, _ f: @escaping(B, A) -> B) -> B {
guard case let .cons(head, tail) = self else {return initialValue}
return tail.foldLeft(f(initialValue, head), f)
}
func foldRight<B>(_ initialValue: B, _ f: @escaping(A, B) -> B) -> B {
guard case let .cons(head, tail) = self else {return initialValue}
return f(head, tail.foldRight(initialValue, f))
}
}
*

Note that `foldRight` is not a tail recursive call as the call to `f` is on the outside.

Again, you will gain more insight into the difference between the two if you will trace the steps in calling `foldRight` in the following cases.

*
fiveSixSeven.foldRight(0, +)
fiveSixSeven.foldRight(0){(element, accumulator) in
accumulator + element
}
fiveSixSeven.foldRight(emptyList){(element, accumulator)
in accumulator.append(element + 1)
}
*

This time the results are `18`, `18`, and `(6(7(8( ))))`, respectively.

A little less space efficient but our answer is in the desired order.

.We now have some very powerful building blocks.

Next time we'll write a method to reverse the order of elements in a list. Then we can write `foldRight` in terms of `foldLeft` and `reverse`. We'll also write `map` and `filter`.