On the elementsEqual problem, or “[Pitch] Set and Dictionary should not be Sequences”

Evolution Pitches
30

It's flawless when considered completely separately from their (also flawless) implementations of Equatable. The problem is what happens when these two aspects get together. In the elementsEqual case, some want to leave the name alone because it makes perfect sense for Sequence, where ordering is salient, and others need to change it because it makes no sense whatever for Set, where ordering isn't salient. But it's easy to find problems beyond sensibility for the reader.

This works fine for all Collections:

extension Collection where Element : Comparable {
    func isSorted() -> Bool { 
        return !zip(self, self.dropFirst()).contains { $0 > $1 }
    }
}

But memoize it, and it stops working for Set.

var memo: [AnyHashable : Bool] = [:]
extension Collection where Self : Hashable, Element : Comparable {
    func isSorted() -> Bool {
        if let r = memo[self] { return r }
        let r = !zip(self, self.dropFirst()).contains { $0 > $1 }
        memo[self] = r
        return r
    }
}

Now, you might say, “serves you right for asking whether a Set is sorted,” but of course nobody asks that question directly. It will happen as part of an order-independent algorithm, to which passing a Set is perfectly sensible:

// Avoid building a new array if x is already sorted.
return x.isSorted() ? something(x) : something(x.sorted())

Yes, this example is somewhat contrived, but it makes my point: the clash of the fundamental notion of equality with the properties of Sequence has effects that you can't reason about locally. Which programmer is to blame for the bug I just constructed? I can't blame the person who memoized isSorted; that's supposed to be a semantics-preserving transformation for all functions without side-effects. When you can't find a programmer to blame for a bug it's a good sign that there's something broken in the system they've been given to work with.

FWIW, I have been scrutinizing approaches to (and definitions of) this problem for years. Until now I didn't have the insight needed to have confidence in a solution.

4 Likes