# 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 `List`s.

*
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 `List`s.

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`.