The Quest for a Heterogeneous Collection of Equatables

April 4, 2016

For a few weeks I’ve been working on a new iOS app, written in Swift. The problem domain is super simple: it’s just a list of what I’m calling “reminder snippets” – for now, basic Title / Value pairs – that are editable in the app, and show up in a Today View Snippet.

Having the problem domain so small allows me to experiment with Swift and potential architectures. I’ve been incorporating some lessons I learned from colleagues at my last job, like using immutable model objects (Swift structs, naturally, for value semantics) and Repositories that are responsible for persistence, caching, and so on.

Protocols

I took the Protocol Oriented Programming talk from last year’s WWDC to heart, so every abstraction in the app is a protocol. (I’ve already written a bit about this talk here.) Specifically, I have a ReminderRepository protocol (with MockReminderRepository and PlistReminderRepository implementations) and a Reminder protocol, with one incredibly simple implementation.

public typealias ReminderID = String

public protocol Reminder{
    var id : ReminderID { get }
    var title : String { get }
    var value : String { get }
}

public protocol ReminderRepository {
    func getAllReminders(callback: Result<[Reminder]> -> Void)
    func getReminder(by id: ReminderID, callback: Result<Reminder> -> Void)
    func addReminder(reminder: Reminder, callback: VoidResult -> Void)
    func deleteReminder(reminder: Reminder, callback: VoidResult -> Void)
}

(Result is just a Success/Fail enum that contains some value on success and an error on failure)

Equatable

So far, so good. I really like this architecture. But problems start to crop up when I need to be able to compare Reminders, for instance, in an implementation of deleteReminder:

public func deleteReminder(reminder: Reminder, callback: VoidResult -> Void) {
    // Error. Can't call indexOf because reminder doesn't conform to Equatable
    if let index = reminders.indexOf(reminder) {        
        reminders.removeAtIndex(index)
        callback(.Success)
    } else {
        callback(.Failure)
    }
}

But if we make Reminder conform to Equatable, we lose the ability to have a heterogeneous array of types that conform to Reminder. (Details are in the Protocol Oriented Programming talk. Seriously, watch it.)

The solution given in the talk for general-case comparison is to implement an extension on our protocol. I thought I’d be clever and factor this out into a new protocol, HeterogeneousEquatable, and have Reminder extend from that.

public protocol HeterogeneousEquatable {
    func isEqual(other : Any) -> Bool
}

public extension HeterogeneousEquatable where Self : Equatable {
    public func isEqual(other : Any) -> Bool {
        if let typedOther = other as? Self {
            return typedOther == self
        }
        return false
    }
}

public protocol Reminder : HeterogeneousEquatable { /* ... */ }

Array.indexOf()

Now returning to the reason I initially wanted to make Reminders Equatable – so that I can call reminders.indexOf(someReminder). Right now we still can’t do that, because while we have roughly equivalent functionality, it doesn’t come under the auspices of the Equatable protocol.

Okay, so what if we just extend Array ourselves?

public extension Array where Element : HeterogeneousEquatable {
    func indexOf(element : Element) -> Index? {
        return indexOf({ (currentElement : Element ) -> Bool in
            element == currentElement
        })
    }
}

Great! Everything still compiles. Now we just have to call our overloaded implementation of indexOf:

public func deleteReminder(reminder: Reminder, callback: VoidResult -> Void) {
    // Error again. Sad face.
    if let index = reminders.indexOf(reminder) {        
        reminders.removeAtIndex(index)
        callback(.Success)
    } else {
        callback(.Failure)
    }
}

Now we get Using "Reminder" as a concrete type conforming to protocol "HeterogeneousEquatable" is not supported. Which is true. Reminder isn’t a concrete type. This is a shortcoming in the compiler; it needs things to be nailed down to concrete types here. One can assume that the reason for this is compiler implementation rather than an intentional limitation of the language at a design level. There’s a great Stack Overflow answer by Rob Napier on this.

A Mediocre Solution

Austin Zheng has a blog post about building a HeterogeneousEquatable (which he calls AnyEquatable), which is a good resource if you found my post hard to follow, but he doesn’t look at the case of implementing an extension on Array.

I asked about this on the swift-users mailing list, and Hooman Mehr pointed out that the best way to achieve this is to write a method in an unconditional extension on Array:

extension Array {
    func indexOf(element : HeterogeneousEquatable) -> Index? {
        return self.indexOf { (currentElement : Element) -> Bool in
            if let currentElement = currentElement as? HeterogeneousEquatable {
                return element.equals(currentElement)
            }
            return false
        }
    }
}

This makes me sad. It forces me to pollute the interface of Array with stuff that doesn’t apply in most cases, and it causes confusion about which implementation of indexOf will be called in an instance of [MyType] where MyType implements both Equatable and HeterogeneousEquatable. (The other option is to name it indexOfAny, as Hooman suggests, but I don’t much like that either.)

A Better Solution, Sometimes

I took my quest to the swift-evolution mailing list, and got better results, but they only apply in certain situations.

Dave Abrahams (the guy who gave the Protocol Oriented Programming talk in the first place!) showed that while we can’t use a value of type HeterogeneousEquatable (where the concrete type is unknown) where the requirement is Element : HeterogeneousEquatable, we can do that when the requirement is Element == HeterogeneousEquatable. That’s awesome!

But.

That means that the variable must be typed explicitly as HeterogeneousEquatable. Reminder, even though it extends from HeterogeneousEquatable, is not acceptable.

public extension CollectionType where Generator.Element == HeterogeneousEquatable {
    func indexOf(item: Generator.Element) -> Index? {
        return indexOf {
            return item.isEqual($0)
        }
    }
}

// ...

public func deleteReminder(reminder: Reminder, callback: VoidResult -> Void) {
    if let index = reminders.indexOf(reminder) {        
        reminders.removeAtIndex(index)
        callback(.Success)
    } else {
        callback(.Failure)
    }
}

Type HeterogeneousEquatable does not conform to protocol 'Reminder'

Conclusion

I’ve had to go ahead with the unconditional extension of Array. It’s the only thing that works properly for my use case, at least today.

It is my desperate hope that future versions of Swift will allow for this kind of abstraction – or just go ahead and solve the Equatable problem in a first-party way.

Denouement

Back when the WWDC talk was new there was a big kerfuffle in the Apple development community about the problem of heterogeneous collections of things that conform to a single protocol – how the decision to split protocols into “has Self requirements” and “doesn’t have self requirements” worlds was benefiting the compiler at the expense of the programmer. Michael Tsai has a good overview of the various blogs from that time, all of which are worth a read, including this post from Brent Simmons:

Something like this ought to come naturally and easily to a language, or else that language is not helping me write apps.

I’m generally very positive on Swift – I think when Swift 3.0 hits and the language starts to change a little more slowly, it will be the obvious choice for future projects – but it has some sharp edges for the time being, and if I was to start a production-ready project today, I’m not entirely sure whether I’d choose Swift or Objective-C.

∞