List map/flatMap

March 25, 2018

Let's extend our look at List and map() to flatMap() and beyond.

Suppose you have a List of Lists.


let lists 
    = List.cons(head: twoThreeFour,
                tail: List.cons(head: fiveSixSeven,
                                tail: List.cons(head: sixSevenEight,
                                                tail: List.empty)))

What if instead we want to combine two lists into a single list? The append() method does this.


extension List {
    func append(_ otherList: List) -> List {
        return foldR(otherList){(a,b) in List.cons(head: a, 
                                                   tail: b)}
    }
}

We can use it like this.


let listsA = twoThreeFour.append(fiveSixSeven)
                         .append(sixSevenEight)

Notice that lists and listsA are different types.

We want a join() method that could turn lists into listsA.

The signature of join() is a tough one. We want to end up with List<A> given that our input is List<List<A>>. Thanks to Rob Napier for clarifying what's possible with the current state of Generics in Swift 4.


extension List {
    func append(_ otherList: List) -> List {
        return foldR(otherList){(a,b) in List.cons(head: a, 
                                                   tail: b)}
    }
    
    func join<B>() -> List<B> where A == List<B> {
        return foldR(List<B>.empty, {(a,b) in a.append(b)})
    }
}

You can see that lists.join() is the same as listsA.

One place we can use join() is in an implementation of flatMap(). In general, flatMap() is a lot like map(). The difference is that map() accepts a function from (A) -> B while flatMap() accepts a function from (A) -> List<B>.


extension List {
    func append(_ otherList: List) -> List {
        return foldR(otherList){(a,b) in List.cons(head: a, 
                                                   tail: b)}
    }
    
    func join<B>() -> List<B> where A == List<B> {
        return foldR(List<B>.empty, {(a,b) in a.append(b)})
    }

    func flatMap<B>(_ f: @escaping (A) -> List<B> ) -> List<B> {
        return map(f).join()
    }
}

Use flatMap() like this.


let flatMapDoubleTwoThreeFour
    = twoThreeFour
      .flatMap{x in List.cons(head: x,
                              tail: List.cons(head: x,
                                              tail: List<Int>.empty))}

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

The result is (2(2(3(3(4(4( ))))))).

If we introduce a pure() we can write map() in terms of flatMap() and pure() as usual (this post is not explaining these concepts - just illustrating them in this case. Another post will look into these various functions.)


extension List {
    func append(_ otherList: List) -> List {
        return foldR(otherList){(a,b) in List.cons(head: a, 
                                                   tail: b)}
    }
    
    func join<B>() -> List<B> where A == List<B> {
        return foldR(List<B>.empty, {(a,b) in a.append(b)})
    }
    
    func flatMap<B>(_ f: @escaping (A) -> List<B> ) -> List<B> {
        return map(f).join()
    }

    init(pure a: A) {
        self = List.cons(head: a, tail: List.empty)
    }
    
    func mapAlt<B>(_ f: @escaping (A) -> B) -> List<B> {
        return flatMap{a in List<B>(pure:(f(a)))}
    }
}

For completeness in this sort of demo, here's apply()


extension List {
    func append(_ otherList: List) -> List {
        return foldR(otherList){(a,b) in List.cons(head: a, 
                                                   tail: b)}
    }
    
    func join<B>() -> List<B> where A == List<B> {
        return foldR(List<B>.empty, {(a,b) in a.append(b)})
    }
    
    func flatMap<B>(_ f: @escaping (A) -> List<B> ) -> List<B> {
        return map(f).join()
    }
    init(pure a: A) {
        self = List.cons(head: a, tail: List.empty)
    }
    
    func mapAlt<B>(_ f: @escaping (A) -> B) -> List<B> {
        return flatMap{a in List<B>(pure:(f(a)))}
    }

    func apply<B>(_ fs: List<(A) -> B>) -> List<B> {
        return fs.foldR(List<B>.empty){
            let f = $0
            return $1.append(self.foldR(List<B>.empty){
                List<B>.cons(head: f($0), tail: $1)
            })
        }
    }
}

Today's code comes from this sample code and here's the Playground it comes from.

That's the end of our look at Lists.

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.