Map and Flatmap

This week, I explained to my colleagues what's the difference between a map and a flatMap1. The trick was: focus on the types and leave the burritos for lunch time.

Map

[a] -> (a -> b) -> [b]

[1,2,3].map { $0*2 }

FlatMap

[a] -> (a -> [b]) -> [b]

[1,2,3].map { [$0*2] }

Assuming that flatMap uses map 2 internally:

func flatMap(f : Int -> [Int]) -> [Int] {  
   return map(f)
}

With that in place, let's see how it would end up looking:

Int -> (Int -> [Int]) -> [[Int]]

If you look closely at how map works, you can see that it takes a function:

a -> b

And returns a:

[b]

The key here, is that you pass a function of type:

a -> [b]

So the outcome:

[[b]]

Wait a sec, but flatMap returns a [b] and we get back a [[b]]. That's true, so that's why you need to flat it:

func flat(v : [[Int]]) -> [Int]  
{
  return v.reduce([], combine: +)
}

As you might have guessed by now, I lied to you. That flatMap's implementation is wrong. A correct one would look like the following:

func flatMap(f : Int -> [Int]) -> [Int] {  
   return flat(map(f))
}

So the entire thing internally looks like this:

[a] -> (a -> [[b]]) -> ([[b]] -> [b]) -> [b]

And to the consumer:

[a] -> (a -> [b]) -> [b]

Unfortunately, Swift doesn't really help understanding these two operators 3:

let a : [Int] = [1,2,3,4] . flatMap { [2 * $0] } // <- This works  
let b : [Int] = [1,2,3,4] . map { 2 * $0 } // This works as well  
let c : [Int] = [1,2,3,4] . flatMap { 2 * $0 }   // <- This works, but in theory it shouldn't(?)  

I will explore why you should use one over the other, in another post.

  1. It was actually about monads, but we need first maps and flatMaps.

  2. I could use generics, but to keep it simple, I will fix the type.

  3. Ben does an awesome job describing these.