The Culmination: Part I

A big part of programming productively is figuring out the right level of abstraction for any given problem. The answer is not unique, though; there are many approaches to solving the same problem: procedural, object-oriented, functional, etc. Some are better supported in some languages than others, and to a degree what we can use depends on the language we choose. For its part, Swift allows us to idiomatically bring functional abstractions into Cocoa development, which is a big boon—as long as we know how to recognize the patterns that call for them.

Among these patterns, there is one that is fundamental. So much so that I have struggled for several weeks over this post, the culmination of my posts on optionals and error-handling, and I’m still unsatisfied with the result. It’s tempting to treat it as a borderline axiom: as something that can’t be explained, merely recognized in action and used for its power. But I have enough hubris to at least attempt to present a way to conceptualize it. Before we get there, though, let me show it, once again, at work.

• • • • •

Merchant Mary has a little business that is open some days of the year. She has those days in a list. On each day, she sells some items. She wants a list of all the items she has sold during the year. Here’s one way to do it:

let daysOpen:[Day] = … // array of days

var items = [Item]()
for day in daysOpen {
    // itemsSoldForDay -> [Item] 
    items += itemsSoldForDay(day)
}

What if for each day she has a function that returns the number of deliveries that arrived? Calling it deliveriesForDay, here’s how Mary obtains the number of deliveries during the year:

var deliveries = [Delivery]()
for day in daysOpen {
    // deliveriesForDay -> [Delivery]
    deliveries += deliveriesForDay(day)
}

Nothing earth-shattering here. But this code is exactly the same as the items code, except for the function (itemsForDay vs. deliveriesForDay). And in Swift, functions are first class objects, so we should be able to create a function that takes either itemsForday or deliveriesForDay and does that exact operation.

At the same time, we might want to chain several calls to this function. For instance what if Mary wants to go further back in time? She wants to start with a list of years, and a function that, for every year, returns the days her business was open. Without this higher order function (what we call functions that take functions as parameters), it would look like this:

let yearsOpen:[Year] = … // the years

var daysOpen = [Day]()
for year in yearsOpen {
    // daysOpenForYear -> [Day]
    daysOpen += daysOpenForYear(year)
}

var cumulativeItems = [Item]()
for day in daysOpen {
    cumulativeItems += itemsSoldForDay(day)
}

In this case, it would be great to have an infix operator that we can chain, so we can get deeper (items per delivery) or go further back in time (locations open for a year or more). Let’s call it >>=-¹ and write it out; it’s pretty simple:²

infix operator { associativity left }
func >>=-<A,B>(elements:[A], f:A -> [B]) -> [B] {
    var result = [B]()
    for elem in elements {
        result += f(elem)
    }
    return result
}

And now getting all the items for a number of years becomes:

let items = yearsOpen >>=- daysForYear >>=- itemsForDay

The other two examples are:

let itemsFromAllLocations = locations >>=- yearsOpenForLocation >>=- 
    daysOpenForYear >>=- itemsSoldForDay

let itemsFromAllDeliveries = daysOpen >>=- deliveriesForDay >>=-
    itemsForDelivery

The operator hides a lot of logic, but it’s simple, repetitive logic, so that’s okay—it becomes part of the domain knowledge of arrays. But now, looking at its type signature, we can notice something. If you [recall][understanding-optionals], the type signature of the |- operator I used to mimic ?. in my post on optionals was:

(optional:A?, f: A -> B?) -> B?

That’s uncannily similar to the type signature for >>=-:

(array:[A], f: A -> [B]) -> [B]

Clearly, there’s something here that’s even more general than operating on just lists or just optionals. And, since we showed that |- could be rewritten as flatMap for optionals, it’s clear that we can rewrite >>=- as flatMap for arrays. Therefore, if we rename |- to >>=- for consistency we have established a new abstraction.

This is an abstraction that operates on structures. By structure, I mean a generic type—in this case of one type variable—which defines some context for the parameter type. For instance, the Array structure defines a list of elements of its parameter type, and the Optional structure defines the presence status of its parameter type. You can think of it as additional information: “any number of Ints”, “an Int, but it might not exist.”

What we end up with is a very generic signature, where M is some structure:

infix operator { associativity left }
func >>=-<A,B>(structure:M<A>, f:A -> M<B>) -> M<B>

M<A> could potentially be Optional<A>, Array<A>, Set<A>, Tree<A>, [Result<A>][mm-2]—any single-parameter generic type. This doesn’t mean, however, that every one of these types needs this abstraction, or that it makes sense to define >>=- for each of them; it only means that the type signature supports it.

The tricky part is understanding what the signature represents. We are used to abstractions representing operations: I take a list, get a list for each item in it, and concatenate them. I take an optional, see if it represents a value, and if it does I compute the next optional. But >>=- is an abstraction over these abstractions, and that makes it closer to a pattern,³ one that can have many manifestations depending on the specific structure that we’re looking at.

Okay, that’s fair, but doesn’t tell us much. Do we have any guidance about what implementations of >>=- should look like? Are all functions that implement the required type signature for >>=- created equal? After all, this function meets the requirements for arrays:

func >>=-<A,B>(elements:[A], f:A -> [B]) -> [B] {
    if (elements.count == 0) {
        return []
    }

    return f(elements[0])
}

It simply returns f applied to the first element, if it exists, or the empty array otherwise. Granted, it doesn’t solve Mary’s problem, but it does fulfill the contract of the type signature. Maybe our original implementation just happened to fit Mary’s bill; maybe this one will fit a different one. Or is there something inherently better about the first one?

Actually, yes there is. And the answer has to do with the future of Swift and the solution to the vexing problem of unboxing multiple optionals.

Oh, and with one more thing. [Monads.][culmination-ii]

¹ This operator is called “bind” in Haskell. I’m not naming it in the body of the article because of how similar to flatMap it is, and I don’t want to lead to confusion, since every time I’ve shown flatMap, it’s been a method.↩︎