Functor & Friends: Protocol + Tests

I’ve read articles that try to reduce the academic flim-flammery of functors, monads, and similar to concrete syntax by just presenting them as a series of interfaces, or protocols, that must be implemented.

This is reassuring: It turns something unfamiliar into something familiar, if not downright mundane. Unfortunately, reducing these abstractions to protocols alone oversimplifies them and reduces their practical utility tremendously.

What gives functional programming abstractions their oomph is the properties satisfied by the abstraction, not the specific API. These properties provide essential guarantees about the implementation of that API. Using these properties lets us reason about our code without getting bogged down in details of the implementation: The dream of meaningful abstraction lives on in FP.

Protocols alone are not powerful enough to specify this. Fortunately, there is a way for object-oriented programmers to return the foreign concept of “mathematical abstraction” to a comfortable familiarity without losing reasoning power. This is by recasting the abstraction in terms of protocols AND tests. The tests specify properties that implementations of those protocols must satisfy in order to truly conform to the protocol.

Together, protocols and tests capture the essence of functional abstractions in a way that an OO programmer can immediately be productive with.

(It’s an interesting observation that, as in TDD, these tests have more value than the protocols themselves.)

Example: Functor

You might see Functor explained like this:

• Functor is a parameterized type with a map function, where
• The map function takes an instance of the type and applies a function from its parameterized type to another instance with a potentially different type parameter.

Or, more concisely, in pseudo-Swift:

map(container: Container<Type>, function: Type -> PotentiallyOtherType)
  -> Container<PotentiallyOtherType>

The protocol fails us: permuting map

A protocol captures only the superficial elements of Functorhood. For example, this implementation of map on an array satisfies the protocol:

func map<T, U>(a: [T], f: T -> U) -> [U] {
    let indexes = allIndexes(a)
    let permutedIndexes = permute(indexes)
    var b: [U] = []
    for i in permutedIndexes {
        let element = a[i]
        let mappedValue = f(element)
        b.append(mappedValue)
    }
    return b
}

But it fails to be a Functor.

Try it for yourself: Mapping the identity function repeatedly (map([1, 2, 3, 4], { $0 })) can give results that differ from the input array. (For the identity function, those results will all be permutations of the input array.)

That makes for one frustrating faux-functor!

Tests to the rescue!

This is why it is not enough to have a function with a certain type signature. The heart of the beast is the set of sanity-preserving properties it’s required to conform to.

These properties go by the name of the functor laws; you’ll find equivalent laws for monads and similar abstractions. It’s these laws that make the abstraction meaningful and tractable. Preserving these laws makes the interface a true abstraction, rather than (in the case of functor) simply a generalization of a common imperative programming pattern.

Specifically, a functor must preserve identity and composition:

• Identity Preservation: XCTAssertEqual(id(x), x.map(id))
• Composition Preservation: XCTAssertEqual(x.map(f).map(g), x.map({ g(f($0)) }))

(Unlike the protocol above, here I’m using method syntax, because that composes a bit more readably.)

The XCTest macros aren’t quite up to the task of proving general properties. With something like SwiftCheck, we can get close, though.

Conclusion

To reiterate:

• It’s not the protocol that makes the functor;
• It’s not “you can write an [f]map function”;
• Instead, it is specific properties exhibited by the compound entity of type + functions.
• Concretely: It is protocol + tests.