List map/flatMap

« Default init

Next »

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 flatMapDoubleTwoThreFour
= 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.