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.