Swift Functional Programming - "Optional Bind" vs. "Optional Map"

Question

I've been working through the Functional Programming in Swift book, and I don't really have a good way to understand the differences in a concept introduced in the Optionals chapter.

The pattern when working with optionals tends to be:

if let thing = optionalThing {
    return doThing(thing)
}
else {
    return nil
}

This idiom is handled succinctly with the standard library function map

map(optionalThing) { thing in doThing(thing) }

The book then continues on and introduces the concept of optional binding, which is where my ability to differentiate starts to break down.

The book guides us to define the map function:

func map<T, U>(optional: T?, f: T -> U) -> U?
{
    if let x = optional {
        return f(x)
    }
    else {
        return nil
    }
}

And also guides us to define an optional binding function. Note: the book uses the operator >>=, but I've chosen to use a named function because it helps me see the similarities.

func optionalBind<T, U>(optional: T?, f: T -> U?) -> U?
{
    if let x = optional {
        return f(x)
    }
    else {
        return nil
    }
}

The implementation for both of these methods looks identical to me. The only difference between the two is the function argument they take:

• map takes a function that transforms a T into a U
• optionalBind takes a function that transforms a T into an optional U

The result of "nesting" these function calls hurts my brain:

func addOptionalsBind(optionalX: Int?, optionalY: Int?) -> Int?
{
    return optionalBind(optionalX) { x in
        optionalBind(optionalY) { y in
            x + y
        }
    }
}

func addOptionalsMap(optionalX: Int?, optionalY: Int?) -> Int?
{
    return map(optionalX) { x in
        map(optionalY) { y in
            x + y
        }
    }
}

• The addOptionalsBind function does exactly what you'd expect it to do.
• The addOptionalsMap function fails to compile stating:

  'Int??' is not convertible to 'Int?'

I feel like I'm close to understand what's happening here (and optional integer is being wrapped again in an optional? But how? why? hu?), but I am also far enough away from understanding that I'm not entirely sure of a smart question to ask.

Answer 1

• map takes a function that transforms a T into a U
• optionalBind takes a function that transforms a T into an optional U

Exactly. That is the entire difference. Let's consider a really simple function, lift(). It's going to convert T into T?. (In Haskell, that function would be called return, but that's a bit too confusing for non-Haskell programmers, and besides, return is a keyword).

func lift<T>(x: T) -> T? {
    return x
}

println([1].map(lift)) // [Optional(1)]

Great. Now what if we do that again:

println([1].map(lift).map(lift)) // [Optional(Optional(1))]

Hmmm. So now we have an Int??, and that's a pain to deal with. We'd really rather just have one level of optionalness. Let's build a function to do that. We'll call it flatten and flatten-down a double-optional to a single-optional.

func flatten<T>(x: T??) -> T? {
    switch x {
    case .Some(let x): return x
    case .None : return nil
    }
}

println([1].map(lift).map(lift).map(flatten)) // [Optional(1)]

Awesome. Just what we wanted. You know, that .map(flatten) happens a lot, so let's give it a name: flatMap (which is what languages like Scala call it). A couple of minutes of playing should prove to you that the implementation of flatMap() is exactly the implementation of bindOptional and they do the same thing. Take an optional and something that returns an optional, and get just a single level of "optional-ness" out of it.

This is a really common problem. It's so common that Haskell has a built-in operator for it (>>=). It's so common that Swift also has a built-in operator for it if you use methods rather than functions. It's called optional-chaining (it's a real shame that Swift doesn't extend this to functions, but Swift loves methods a lot more than it loves functions):

struct Name {
    let first: String? = nil
    let last: String? = nil
}

struct Person {
    let name: Name? = nil
}

let p:Person? = Person(name: Name(first: "Bob", last: "Jones"))
println(p?.name?.first) // Optional("Bob"), not Optional(Optional(Optional("Bob")))

?. is really just flatMap (*) which is really just bindOptional. Why the different names? Well, it turns out that "map and then flatten" is equivalent to another idea called the monadic bind which thinks about this problem a different way. Yep, monads and all that. If you think of T? as a monad (which it is), then flatMap turns out to be the bind operation that is required. (So "bind" is a more general term that applies to all monads, while "flat map" refers to the implementation detail. I find "flat map" easier to teach people first, but YMMV.)

If you want an even longer version of this discussion and how it can apply to other types than Optional, see Flattenin' Your Mappenin'.

(*) .? can also sort of be map depending on what you pass. If you pass T->U? then it's flatMap. If you pass T->U then you can either think of it as being map, or you still think of it being flatMap where the U is implicitly promoted to U? (which Swift will do automatically).

Answer 2

What's happening might be clearer with a more verbose implementation of addOptionalsMap. Let's start with the innermost call to map—instead of what you have there, let's use this instead:

let mappedInternal: Int? = map(optionalY) { (y: Int) -> Int in
    return x + y
}

The closure provided to map takes an Int and returns and Int, while the call to map itself returns an optional: Int?. No surprises there! Let's move one step out and see what happens:

let mappedExternal: ??? = map(optionalX) { (x: ???) -> ??? in
    let mappedInternal: Int? = map(optionalY) { (y: Int) -> Int in
        return x + y
    }
    return mappedInternal
}

Here we can see our mappedInternal value from above, but there are a few types left undefined. map has a signature of (T?, T -> U) -> U?, so we only need to figure out what T and U are in this case. We know the return value of the closure, mappedInternal, is an Int?, so U becomes Int? here. T, on the other hand, can stay a non-optional Int. Substituting, we get this:

let mappedExternal: Int?? = map(optionalX) { (x: Int) -> Int? in
    let mappedInternal: Int? = map(optionalY) { (y: Int) -> Int in
        return x + y
    }
    return mappedInternal
}

The closure is T -> U, which evaluates to Int -> Int?, and the whole map expression ends up mapping Int? to Int??. Not what you had in mind!

---

Contrast that with the version using optionalBind, fully type-specified:

let boundExternal: ??? = optionalBind(optionalX) { (x: ???) -> ??? in
    let boundInternal: Int? = optionalBind(optionalY) { (y: Int) -> Int? in
        return x + y
    }
    return boundInternal
}

Let's look at those ??? types for this version. For optionalBind we need T -> U? closure, and have an Int? return value in boundInternal. So both T and U in this case can simply be Int, and our implementation looks like this:

let boundExternal: Int? = optionalBind(optionalX) { (x: Int) -> Int? in
    let boundInternal: Int? = optionalBind(optionalY) { (y: Int) -> Int? in
        return x + y
    }
    return boundInternal
}

---

Your confusion may come from the way variables can be "lifted" as optionals. It's easy to see when working with a single layer:

func optionalOpposite(num: Int?) -> Int? {
    if let num = num {
        return -num
    }
    return nil
}

optionalOpposite can be called with either a variable of type Int?, like it explicitly expects, or a non-optional variable of type Int. In this second case, the non-optional variable is implicitly converted to an optional (i.e., lifted) during the call.

map(x: T, f: T -> U) -> U? is doing the lifting in its return value. Since f is declared as T -> U, it never returns an optional U?. Yet the return value of map as U? means that f(x) gets lifted to U? on return.

In your example, the inner closure returns x + y, an Int that is lifted to an Int?. That value is then lifted again to Int?? resulting in the type mismatch, since you've declared addOptionalsMap to return an Int?.