List map/flatMap


« Default init

Failure is an Option(al) »

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.