# Building on our Foundation

February 15, 2018

Last time we created `foldLeft` and `foldRight` for `List`.

We looked at two examples of using these methods. The first just summed the elements of the list. Although `foldRight` was left efficient, both methods gave us the same results. The second example added one to each element of the list. This revealed that although `foldRight` was less efficient, it gave us the results we expected while `foldLeft` reversed the `List` as it processed it.

Hmmm.

We can use `foldLeft` to reverse a `List` without altering it in any other way.

Once we do that, we can write a version of `foldRight` in terms of `foldLeft`.

Take a moment and try to write `reversed` using `foldLeft`.

Here's a possible solution.

*
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))
}
func reversed() -> List {
return foldLeft(List.empty){ (reversedList, element) in
List.cons(head: element, tail: reversedList)
}
}
}
*

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.

Use `reversed` like this to reverse `twoThreeFour`.

*
twoThreeFour.reversed()
*

The result is `(4(3(2( ))))`. Also you can check that `emptyList.reversed()` is `emptyList.`.

Actually, it might be handy to define `==` for `List`.

*
extension List: Equatable where A: Equatable {
static func == (lhs: List, rhs: List) -> Bool {
switch (lhs, rhs) {
case (.empty, .empty): return true
case(.empty, .cons), (.cons, .empty): return false
case(.cons(let headL, let tailL),
.cons(let headR, let tailR)):
return headL == headR && tailL == tailR
}
}
}
*

Now we can check that when we reverse `twoThreeFour` we get something different but when we reverse the reversed list we get back to what we started with. We can also test that when we reverse `emptyList` the result is the same as `emptyList`. In other words, the results for the following:

*
twoThreeFour == twoThreeFour.reversed()
twoThreeFour == twoThreeFour.reversed().reversed()
emptyList == emptyList.reversed()
*

is `false`, `true`, and `true`.

OK, let's get back to using `foldLeft` and `reversed` to write a variant 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))
}
func reversed() -> List {
return foldLeft(List.empty){ (reversedList, element) in
List.cons(head: element, tail: reversedList)
}
}
func foldR<B>(_ initialValue: B,
_ f: @escaping(A, B) -> B) -> B {
return reversed().foldLeft(initialValue){(b,a) in f(a,b)}
}
}
*

This is the part I just love.

We've built a solid foundation and can now take advantage of the pieces to add functionally without too much more work.

Let's use `foldR`.

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

Nice.

The results are the same as for `foldRight`. The elements are in the expected order when we add one to each entry in the list `fiveSixSeven`: `(6(7(8( ))))`.

Of course this application of `foldR` feels like `map`. Let's implement `map` in terms of `foldR`.

The `map` function needs to accept a function that tells us how to transform an element of type `A` to an element of type `B`. We build up our mapped list by applying the function to each element and cons-ing it as the head of the existing list.

*
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))
}
func reversed() -> List {
return foldLeft(List.empty){ (reversedList, element) in
List.cons(head: element, tail: reversedList)
}
}
func foldR,B>(_ initialValue: B,
_ f: @escaping(A, B) -> B) -> B {
return reversed().foldLeft(initialValue){(b,a) in f(a,b)}
}
func map<B>(_ f: @escaping (A) -> B) -> List<B> {
return foldR(List<B>.empty){(element, mappedList) in
List<B>.cons(head: f(element), tail: mappedList)}
}
}
*

We can use `map` like this.

*
let sixSevenEight = fiveSixSeven.map{x in x + 1}
*

`sixSevenEight` is `(6(7(8( ))))`.

Before we wrap up, implement `filter`.

*
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))
}
func reversed() -> List {
return foldLeft(List.empty){ (reversedList, element) in
List.cons(head: element, tail: reversedList)
}
}
func foldR<B>(_ initialValue: B,
_ f: @escaping(A, B) -> B) -> B {
return reversed().foldLeft(initialValue){(b,a) in f(a,b)}
}
func map<B>(_ f: @escaping (A) -> B) -> List<B> {
return foldR(List<B>.empty){(element, mappedList) in
List<B>.cons(head: f(element), tail: mappedList)}
}
func filter(_ f: @escaping (A) -> Bool) -> List {
return foldR(List.empty){(element, filteredList) in
f(element) ? List.cons(head: element,
tail: filteredList) : filteredList}
}
}
*

We can use `filter` to pull the even numbers out of `sixSevenEight` or to pull out the numbers less than or equal to `7`.

*
let evens = sixSevenEight.filter{x in x % 2 == 0}
let sixSeven = sixSevenEight.filter{x in x ,= 7}
sixSeven
*

The results are `(6(8( )))` and `(6(7( )))` respectively.

We've built `reversed` and `foldR` on top of `foldLeft`. We then build `map` and `filter` on top of `foldR`. It reminds me of high school geometry. We work to prove a couple of theorems and then we mine them for a whole bunch of other results.