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.