App Development

A Tale of Two flatMaps

tale-of-two-flatmaps blog-featured-image it-510x296

Playground alert! For the technically inclined, an Xcode playground of this whole post can be downloaded here.

Frequently on the iOS team we’ll use the Swift flatMap standard library method to remove nil values from a sequence of optionals, like so:

let a: [Int?] = [1, 2, 3, nil, 5]
let b = a.flatMap { $0 }
print(b)
// => [1, 2, 3, 5]

But did you know that there’s another flatMap in the standard library? And did you know that there’s a bug in the Swift compiler that an examination of the two exposed?

Our team recently explored the flatMap methods in depth and discovered that sometimes interactions with the compiler are not always intuitive!

The Two flatMaps

Above we saw how to use flatMap to remove nil values from a SequenceType of optional values. So let’s check the output of the following:

var a = [[1,2],[3,4]]
let b = a.flatMap { $0 }
print(b)
// => [1, 2, 3, 4]

Whoa! Assuming that flatMap removes nil values, we might expect b to be [[1,2],[3,4]], since there are no nil values. Instead we get [1,2,3,4], a value of type [Int] rather than [[Int]]. What’s going on?

And here’s another interesting thing: What if we assign the result of flatMap back to a? Surely that can’t compile, because if it is returning [Int] and a is of type [[Int]], then there should be an error.

a = a.flatMap { $0 }
print(a)
// => [[1, 2], [3, 4]]

Another whoa! This time it returns the results we expected the first time. But actually, we know that [1,2,3,4] could not have been a valid value for a anyway, since that does not fit its type of [[Int]].

Here we have two results of flatMap that look like the same call, returning two different types depending on what it’s being assigned to. Since Swift is strongly typed, this points to only one thing: method overloading. Although deduction works, we can also go dig into the standard library to see (⌘-click on the method name from Xcode).

Doing that, we see the following two method definitions (adjusted here to compile in playgrounds).

extension SequenceType {
    /// Return an `Array` containing the concatenated results of mapping
    /// `transform` over `self`.
    ///
    /// s.flatMap(transform)
    ///
    /// is equivalent to
    ///
    /// Array(s.map(transform).flatten())
    ///
    /// - Complexity: O(*M* + *N*), where *M* is the length of `self`
    /// and *N* is the length of the result.
    @warn_unused_result
    public func flatMap<S : SequenceType>(transform: (Self.Generator.Element) throws -> S) rethrows -> [S.Generator.Element]
}

extension SequenceType {
    /// Return an `Array` containing the non-nil results of mapping
    /// `transform` over `self`.
    ///
    /// - Complexity: O(*M* + *N*), where *M* is the length of `self`
    /// and *N* is the length of the result.
    @warn_unused_result
    public func flatMap<T>(@noescape transform: (Self.Generator.Element) throws -> T?) rethrows -> [T]
}

So what’s the story about these two flatMap definitions?

My usage of flatMap has always been to strip nil values; it surprised me to learn that there was a version that called flatten to flatten out nested arrays. Humorously, this is the opposite reaction that Natasha the Robot wrote about last summer.

Why are there two versions that behave differently? A tweet linked in the above article helps shed some light. tale-of-2-flatmaps blog-post-image IT So rather than having a mental model of flatMap as “stripping nils,” or as “flattening arrays,” we can settle on a more inclusive mental model where flatMap is thought of as “pulling items out of containers.”

Let’s walk through each of those method definitions with our nested array example.

Demystifying the generics via type inference

Given our last snippet with nested arrays, we can see when we dive in that when assigned to a new variable b,the specific method being called is the one with the SequenceType constraint.

let a = [[1,2],[3,4]]
let b = a.flatMap { $0 }

This is the definition used:

extension SequenceType {
@warn_unused_result
public func flatMap<S : SequenceType>(transform: (Self.Generator.Element) throws -> S) rethrows -> [S.Generator.Element]
}

We can de-genericize it and gain insight into the type inference the compiler is doing like so:

  • Since a is of type [[Int]], then Self.Generator.Element is [Int].
  • The closure we are passing returns its input as its output; so S is also [Int].
  • This means that the return value of flatMap, [S.Generator.Element], is an array of the inner element type of S; so if S is [Int] an array of its element type is also of type [Int].

That matches our return value and our adjusted expectations:

print(b)
// => [1, 2, 3, 4]
print(b.dynamicType)
// => Array<Int>

But it’s a different story when re-assigned to a. When our a is assigned back to itself, we can see when we ⌘-click on flatMap that the other flatMap method is being called.

var a = [[1,2],[3,4]]
a = a.flatMap { $0 }

This time, this is the definition used:

extension SequenceType {
   @warn_unused_result
   public func flatMap<T>(@noescape transform: (Self.Generator.Element) throws -> T?) rethrows -> [T]
}

Let’s do the same de-genericization on it:

  • Since a is of type [[Int]], and the return value of flatMap must be [[Int]].
  • Since the return value of flatMap is declared as [T], that means that T is [Int].
  • That in turn implies that the return value of the transform closure is [Int]?.

That doesn’t quite match our expectations. It looks like we’re returning the same input as the output in that closure; and we are! So what’s going on?

What we are not doing is fully specifying the type of the closure we’re passing in. It looks to us like it’s of type ([Int])->([Int])but it’s actually of type ([Int])->([Int]?). Our return value is valid because you can return a non-optional value and it satisfies an optional return value, like so:

func returnOptionalFromNonOptional() -> Int? {
   let i = 1
   print(i.dynamicType) // => "Int"
   return i
}
let j = returnOptionalFromNonOptional()
print(j.dynamicType)
// => "Optional<Int>"

Inside the method above, i is of type Int. But since a guaranteed value satisfies an optional value, the compiler automatically wraps it in a value of type Int? for us when we return it. Using the generic syntax for optionals for which ? is syntactic sugar, the final value returned is Optional.Some(1).

So that makes sense! And it matches our expectations again. We thought we were returning [Int], but we were actually returning an [Int]? which the compiler accepted and wrapped, and now we’re stripping nils from the array again (of course, there aren’t any).

print(a)
// => [1, 2], [3, 4]]

It could be a good idea to add clarity to our transform closure so that returning a value of type [Int]? as an [Int]? doesn’t seem confusing. Let’s do that next.

Ok, for clarity and giggles in this contrived example, let’s tell the compiler the type of the closure we’re going to use as flatMap’s transform. Of course, I expect this not to compile because the expected closure must return [Int]?, not [Int].

var a = [[1,2],[3,4]]
let transform: ([Int])->([Int]) = { $0 }
a = a.flatMap(transform)
print(a)
// => [[1, 2], [3, 4]]

What!? This compiles and runs with the same results as last time (in Xcode 7.1 and higher).

We seem to be caught in a contradiction of types! Remember what we deduced last time. Given that it’s using the following method:

extension SequenceType {
   @warn_unused_result
   public func flatMap<T>(@noescape transform: (Self.Generator.Element) throws -> T?) rethrows -> [T]
}

We know that the type of a as [[Int]] means that flatMap’s return value must be [[Int]], so T must be [Int]. But this time, we know that the return value of our transform closure is [Int], when flatMap expects the closure to return T?, or [Int]?. That seems like a contradiction!

In fact, in Swift 2.0 this code behaves “as expected” and does not compile! The compiler tells us:

error: function signature '([Int]) -> ([Int])' is not compatible with expected type '([Int]) throws -> [Int]?'

So what happened in Swift 2.1 that lets it work now? The answer is analogous to our last closure returning an [Int] as an [Int]? due to the compiler accepting and wrapping the non-optional type in its optional version. In fact, the reason that works is because for all types, type T is covariant with T?: it is a subtype. Everywhere you expect “maybe” a value, “definitely” having a value suffices.

The property of covariance also applies to derived types, like closures returning values. This time our transform is being accepted by flatMap because it is covariant with the expected closure type. Swift 2.1 added covariance and contravariance support to functions and closures.

This can continue through any number of layers of optionality:

func wrapped(closure: ([Int])->([Int]???)) -> [Int]????? {
   let i = [Int]()
   return closure(i)
}


let b = wrapped(transform)
print(b)
// => Optional(Optional(Optional(Optional(Optional([])))))
print(b.dynamicType)
// => Optional<Optional<Optional<Optional<Optional<Array<Int>>>>>>

But all of this (ultimately) makes sense, while I promised you a bug in the compiler! Let’s look at that next.

The bug

What if we go back to our case of arrays of optionals?

var a: [[Int]?] = [[1,2],[3,4],nil]
let b = a.flatMap { $0 }
print(b)
// => [[1, 2], [3, 4]]

That fits our new mental model, too. Instead of the container in a being an array, the container in a is an optional. Since Optional does not conform to SequenceType when we call flatMap it hits the version that strips nil values, and returns us an array of non-optional [Int] values.

print(b.dynamicType)
// => Array<Array<Int>>

What if we reassign back to a?

a = a.flatMap { $0 }
print(a)
// => [Optional([1, 2]), Optional([3, 4]), nil]

Now the same method returns nil as a valid value. This makes sense, because of how the type of closure is inferred.

Remember that the closure in this case must return a type of T? where the ultimate return type of T is restricted to [Int]?. And a nil value for [Int]? is a valid value for a type [Int]??.

You can consider the closure returning the following values for each item in a: .Some([1,2]), .Some([3,4]), .Some(.None).

You can see that in the following example:

func returnOptionalOptionalFromOptional() -> Int?? {
    let i: Int? = nil
    return i
}
let j = returnOptionalOptionalFromOptional()
print(j)
// => Optional(nil)
print(j.dynamicType)
// => Optional<Optional<Int>>

Notice that i is of type Int? and has the value .None, while j is of type Int?? and has the value .Some(.None), since .None is a valid value of Int?!

But it turns out it’s a different story when closure covariance support is leveraged. What if we specify the transform closure type in this optional case?

var a: [[Int]?] = [[1,2],[3,4],nil]
let transform: ([Int]?)->([Int]?) = { $0 }
a = a.flatMap(transform)
print(a)
// => [Optional([1, 2]), Optional([3, 4])]

Given that if we don’t specify the closure type, the result is [[1,2],[3,4],nil], why should the nil be removed when we specify the closure type?

To show side by side:

let a = [[1,2],[3,4],nil]
let b: [[Int]?] = a.flatMap { (i: [Int]?) -> ([Int]??) in return i }
let c: [[Int]?] = a.flatMap { (i: [Int]?) -> ([Int]?) in return i }
print(b) // => [Optional([1, 2]), Optional([3, 4]), nil]
print(c) // => [Optional([1, 2]), Optional([3, 4])]

We see that when the closure returns [Int]?? it behaves as we expect, and when the closure returns [Int]?, a covariant type, it does not. We think this is a bug, especially considering the promise of covariance is that it it does not affect the behavior of your code. Subtypes should be able to be used interchangeably with the same outcome.

We filed this issue as SR-817 , and it’s been confirmed by Apple engineers as a bug in the compiler.

This short repro case highlights that covariance support for closures is the buggy area:

func takeOptionalOptionalInt(getOptionalOptionalInt: () -> Int??) -> Int?? {
    let value = getOptionalOptionalInt()
    switch value {
    case .Some(.Some(let i)):
        return .Some(.Some(i))
    case .Some(.None):
        return .Some(.None) // Expected
    case .None:
        return .None // Actual
    }
}
let makeNilOptionalInt: () -> Int? = { return .None }
print(takeOptionalOptionalInt(makeNilOptionalInt))
// => nil

Contrast this with the outcome of our earlier returnOptionalOptionalFromOptional which returned the appropriate .Some(.None) value from .None, while the closure support here returns .None erroneously.

Thanks for reading!

And special thanks to my colleagues:

  • Matt Yohe for bringing up this little puzzle
  • Robert Thompson for pointing out the real bug in these examples
  • Kevin Conner for the excellent repro case on the bug report
  • The three engineers above and the rest of the iOS team for our excellent discussion on the topic
Quickstart-Guide-to-Kotlin-Multiplatform

A Quick Start Guide to Kotlin Multiplatform

Kotlin Multiplatform, though still experimental, is a great up-and-coming solution...

Read the article