How flatMap API contract transforms Optional input to Non Optional result?
Asked Answered
H

1

2

This is the contract of flatMap in Swift 3.0.2

public struct Array<Element> : RandomAccessCollection, MutableCollection {
    public func flatMap<ElementOfResult>(_ transform: (Element) throws -> ElementOfResult?) rethrows -> [ElementOfResult]
}

If I take an Array of [String?] flatMap returns [String]

let albums = ["Fearless", nil, "Speak Now", nil, "Red"]
let result = albums.flatMap { $0 }
type(of: result) 
// Array<String>.Type

Here ElementOfResult becomes String, why not String? ? How is the generic type system able to strip out the Optional part from the expression?

Harelda answered 13/2, 2017 at 21:12 Comment(0)
H
4

As you're using the identity transform { $0 }, the compiler will infer that ElementOfResult? (the result of the transform) is equivalent to Element (the argument of the transform). In this case, Element is String?, therefore ElementOfResult? == String?. There's no need for optional promotion here, so ElementOfResult can be inferred to be String.

Therefore flatMap(_:) in this case returns a [String].

Internally, this conversion from the closure's return of ElementOfResult? to ElementOfResult is simply done by conditionally unwrapping the optional, and if successful, the unwrapped value is appended to the result. You can see the exact implementation here.


As an addendum, note that as Martin points out, closure bodies only participate in type inference when they're single-statement closures (see this related bug report). The reasoning for this was given by Jordan Rose in this mailing list discussion:

Swift's type inference is currently statement-oriented, so there's no easy way to do [multiple-statement closure] inference. This is at least partly a compilation-time concern: Swift's type system allows many more possible conversions than, say, Haskell or OCaml, so solving the types for an entire multi-statement function is not a trivial problem, possibly not a tractable problem.

This means that for closures with multiple statements that are passed to methods such as map(_:) or flatMap(_:) (where the result type is a generic placeholder), you'll have to explicitly annotate the return type of the closure, or the method return itself.

For example, this doesn't compile:

// error: Unable to infer complex closure return type; add explicit type to disambiguate.
let result = albums.flatMap {
    print($0 as Any)
    return $0
}

But these do:

// explicitly annotate [ElementOfResult] to be [String] – thus ElementOfResult == String.
let result: [String] = albums.flatMap {
    print($0 as Any)
    return $0
}

// explicitly annotate ElementOfResult? to be String? – thus ElementOfResult == String.
let result = albums.flatMap { element -> String? in
    print(element as Any)
    return element
}
Hothead answered 13/2, 2017 at 21:21 Comment(13)
Perhaps emphasize that the return type is inferred automatically for single-expression closures. albums.flatMap { e in print(e); return e } does not compile.Kramer
While burdensome and surprising, it appears from the bug report discussion that this is actually not a bug!Reest
@Reest Yup, it's just a feature to keep your compile times down :) But completely surprising given the sheer list of other amazing things that the type checker is already able to do.Hothead
The other thing worth noting, which may address the OP's point of confusion, is that flatMap filters the collection such that nil elements in the original collection don't appear in the output collection. That is, ["a", "b", nil, "c", nil].flatMap { $0 } takes an array whose type is implicitly [String?] (because it contains nils) and produces ["a", "b", "c"], whose type is guaranteed to be [String] because it prevents nil elements from occurring in the output.Coniferous
@Coniferous I assumed that OP was solely asking about type inference, rather than the actual implementation of flatMap(_:) – although I'm less sure since his last edit to the question. In any case, I've gone ahead and added a paragraph about the implementation – thanks for raising it :)Hothead
@Coniferous OT but it seems that flatMap not always filters out nil's #42215380 not sure yet if it's a bug or a feature.Harelda
@MaximVeksler flatMap does two completely (?) unrelated things — I've always hated that. It either (1) flattens an array of arrays into a single array, or (2) safe-unwraps an array of Optionals, eliminating any nil elements.Reest
Thanks @Reest now it finally starts to make sense gist.github.com/maximveksler/0afaddcd2c3d6554db572894c20ccdafHarelda
@MaximVeksler Right. See also the discussion in my book apeth.com/swiftBook/… Your use of two chained flatmaps with different meanings is perfectly reasonable.Reest
@Hothead can you please provide further information on the claim that "therefore ElementOfResult? == String?. There's no need for optional promotion here, so ElementOfResult can be inferred to be String." I can't seem to find any documentation that this is indeed what the compiler does when 2 types func foo<A, B>(closure: A -> B?) -> [B] and A is String? so B can become [String]. I'm not sure that this is the only thing that is going on to make this work.Harelda
@MaximVeksler I'm not quite sure I follow, what else would you expect B to become in the example you give? If you're interested in the nitty-gritty details of the type checker, you can take a look at the Type Checker Design and Implementation documentation. From what I understand (the documentation isn't terribly clear about it), the promotion of an optional increases the score of a given solution – therefore a solution that doesn't involve optional promotion will be favoured.Hothead
@Hamish: Please excuse me for pinging you like this (and feel free to simply ignore this), but I would like to invite you to have a look at codereview.stackexchange.com/q/158798/35991 and codereview.stackexchange.com/q/158799/35991. It is about sequences and performance, so you might be interested and perhaps provide valuable feedback.Kramer
@MartinR No problem, I'm always fine with being pinged. The two posts certainly look interesting, and I'll try and have a look at them later today/tomorrow :)Hothead

© 2022 - 2024 — McMap. All rights reserved.