Adding a polymorphic Equatable?

The fact that Equatable isn't polymorphic (related discussion: Rename protocols that use Self or associated types to “constraints”, and declare them as such) has been an immense cause of pain. I'm trying to create a reactive GUI library for Linux and macOS, and part of that relies on being able to compare new widgets to see if they need rebuilding.

My Widget base type is a protocol, that way types that implement it can be structs, meaning that they can take advantage of synthesized Equatable and Hashable conformance.

However, I can't make Widget Equatable, because then it wouldn't be polymorphic. I can't wrap it (something like AnyWidget) to take advantage of type erasure, because then it would be far more verbose for the library's users. I've managed to work around it by having a child key member that is instead compared.

Except == isn't polymorphic (given let a: Base = Derived(), a == a will call func == (a: Base, b: Base), not func == (a: Derived, b: Derived)), so I ended up implementing my own TypeErasedHashable protocol and implementing a polymorphic .equals method.

Now, after all this, I'm kind of wondering why there is no option for a polymorphic equatable. Something like this:

protocol Equatable {
    func == (rhs: Any) -> Bool
}

// Example:

struct MyType: Equatable {
    var value: Int
    func == (rhs: Any) -> Bool {
        guard let rhs = rhs as? MyType else { return }
        return value == rhs.value
    }
}

It's a little more wordy, but it's also far more flexible.

There's always the option of having this one call the top-level == by default, so you could kind of get the best of both worlds.

Thoughts?

2 Likes

This exact topic has been addressed in the Mother of All POP Demos, the "Protocol-Oriented Programming in Swift" conference at WWDC 2015.

The topic starts here in the video (slides 222 and up).

2 Likes

Could someone remind why we need this Self constraint in Equatable ? Performance issues in case of Ryan's variant?
Because otherwise we could have [Equatable] arrays and polymorphic equality.

Sometimes it seems like Self constraint in Equatable is more evil than not having exact type inside '==' implementation(use casting). For example someone could write the code below that looks like OK but is incorrect:

class Base: Equatable {
    static func ==(lhs: Base, rhs: Base) -> Bool {
        print("Base == Base")
        return true
    }
}

class Derived: Base {
    let i = 100
    
    static func ==(lhs: Derived, rhs: Derived) -> Bool {
        print("Derived == Derived")
        return ((lhs as Base) == (rhs as Base)) && (lhs.i == rhs.i)
    }
}

func processTwo(_ a : Base, _ b: Base) {
    if a == b { print("same") } else { print("differ") }
}

func processTwoGeneric<T: Equatable>(_ a : T, _ b: T) {
    if a == b { print("same") } else { print("differ") }
}

processTwo(Derived(), Derived()) // "Base == Base"
processTwoGeneric(Derived(), Derived()) // "Base == Base"

It that Self in Equatable is really worth all the complexity we have now?

1 Like

With generalised existentials, you could still have an Array<Equatable>.

The thing is that you can't just call == with two random objects of type Equatable; you would first need to make sure that the objects are the same type.

The only difference is whether the caller needs to check type-equality (perhaps by binding one type to a local generic parameter, which would come with generalised existentials), or if we leave it to the operator implementation to cast from Any. So you're doing the same thing either way - whether its this generalised existential unboxing or bog-standard dynamic downcasting. I'm not sure either approach really has less complexity than the other.

Right now, it isn't a massive problem, because you don't get collections of heterogenous Equatables. If generalised existentials make it a common problem, we could easily create a version of the operator which conveniently builds-in the unboxing.

5 Likes

Do we have a timeline for generalised existentials? I disagree with your assertion that it's not a massive problem. I use marker protocols that I keep in arrays all the time, I.E.:

protocol ChatEvent: Equatable {}

struct TextChatEvent: ChatEvent {
   text: String
}

struct ImageChatEvent: ChatEvent {
   image: UIImage
}

previousEvents: [ChatEvent] = [// Some events]
newEvents: [ChatEvent] = [// Some events]

Comparing two arrays of those events is such a pain that I've created a protocol "AnonymousEquatable" that does what Ryan said, and then am using code generation to implement it for each struct that follows that protocol. It's easily my biggest pain point with Swift in iOS development right now.

4 Likes

Generic protocols would be better though. If you had Equateable<Int> then the compiler would do the type checking for you and you wouldn’t need to rely on a runtime test. Static type checking is after all one of the reasons we all prefer Swift over Python :wink:.

When I need a versatile Equateable I use double dispatch, e.g.:

protocol MyEquatable {
    func equals<R>(rhs: R) -> Bool where R: MyEquatable
    func equalsReverseDispatch<L>(lhs: L) -> Bool where L: MyEquatable
}

extension MyEquatable {
    /*final*/ func equalsReverseDispatch<L>(lhs: L) -> Bool where L: MyEquatable {
        return lhs.equals(rhs: self) // Fix the type of RHS (as Self).
    }
}

/*final*/ func ==<L, R>(lhs: L, rhs: R) -> Bool where L: MyEquatable, R: MyEquatable {
    return rhs.equalsReverseDispatch(lhs: lhs)
}

class Point2D: MyEquatable {
    let x: Double
    let y: Double
    init(x: Double, y: Double) {
        self.x = x
        self.y = y
    }
    func equals<R>(rhs: R) -> Bool where R: MyEquatable {
        guard let r = rhs as? Point2D else {
            fatalError("Coding Error: Should never be reached.")
        }
        return x == r.x && y == r.y
    }
}

let p20 = Point2D(x: 0, y: 0)
let p21 = Point2D(x: 1, y: 1)
p20 == p20 // T
p20 == p21 // F

// Point3D can be added retrospectively (main point of technique!).
class Point3D: Point2D {
    let z: Double
    init(x: Double, y: Double, z: Double) {
        self.z = z
        super.init(x: x, y: y)
    }
    override func equals<R>(rhs: R) -> Bool where R: MyEquatable {
        if let r = rhs as? Point2D {
            return x == r.x && y == r.y && z == 0 // 2D points lie on the z = 0 plane.
        } else if let r = rhs as? Point3D {
            return x == r.x && y == r.y && z == r.z
        } else {
            fatalError("Coding Error: Should never be reached.")
        }
    }
}

let p30 = Point3D(x: 0, y: 0, z: 0)
let p31 = Point3D(x: 1, y: 1, z: 1)
p30 == p30 // T
p30 == p31 // F

p20 == p30 // T
p30 == p20 // T
p21 == p30 // F
p30 == p21 // F
p20 == p31 // F
p31 == p20 // F
2 Likes

That's roughly what my AnonymousEquatable protocol does.

public protocol AnonymousEquatable {
    func isEqual(_ equatable: AnonymousEquatable) -> Bool
}

func == (lhs: AnonymousEquatable?, rhs: AnonymousEquatable?) -> Bool {
    switch (lhs, rhs) {
    case (.some(let lhs), .some(let rhs)):
        return lhs.isEqual(rhs)
    case (.none, .none):
        return true
    default:
        return false
    }
}

func != (lhs: AnonymousEquatable?, rhs: AnonymousEquatable?) -> Bool {
    return !(lhs == rhs)
}

func == (lhs: [AnonymousEquatable]?, rhs: [AnonymousEquatable]?) -> Bool {
    switch (lhs, rhs) {
    case (.some(let lhs), .some(let rhs)):
        return lhs == rhs
    case (.none, .none):
        return true
    default:
        return false
    }
}

func != (lhs: [AnonymousEquatable]?, rhs: [AnonymousEquatable]?) -> Bool {
    return !(lhs == rhs)
}

func == (lhs: [AnonymousEquatable], rhs: [AnonymousEquatable]) -> Bool {
    return lhs.elementsEqual(rhs, by: { (lhsElement, rhsElement) -> Bool in
        return lhsElement == rhsElement
    })
}

func != (lhs: [AnonymousEquatable], rhs: [AnonymousEquatable]) -> Bool {
    return !(lhs == rhs)
}

And then I make sure all the implementations of it use Equatable, and then use Sourcery to generate the implementation for everything that implements it:

// ChatEvent.swift
protocol ChatEvent: AnonymousEquatable {}

// ChatCallEvent.swift
struct ChatCallEvent: ChatEvent, Equatable {
   ...
}

// AnonymousEquatable.generated.swift
extension ChatCallEvent {
    func isEqual(_ equatable: AnonymousEquatable) -> Bool {
        guard let equatable = equatable as? ChatCallEvent else {
            return false
        }

        return self == equatable
   }
}

I think the point that OP is trying to make is if AnonymousEquatable was the Equatable implementation, this would all be free.

I understand why the limitations are there. I understand boxing, I understand using a separate protocol like AnonymousEquatable. The problem for me is that they're all workarounds for what I feel like I should be able to do, and something that all the other commonly used languages support.

Slight aside: writing equality checks that compare different classes, even subclasses, quickly gets non trivial. @hlovatt's Pount2D / Point3D example results in:

p21 == p31 // T
p31 == p21 // F

The order of the comparison can become important, leading to subtile bugs, and if you add Hashable to you classes expecting to use them as keys, the fun bugs really come out.

7 Likes

As Thomas correctly points out the code I posted was incorrect. Corrected version below:

import Foundation

protocol AnyEquatable {
    func equals(rhs: AnyEquatable) -> Bool
    func canEqualReverseDispatch(lhs: AnyEquatable) -> Bool
}

/*final*/ func ==(lhs: AnyEquatable, rhs: AnyEquatable) -> Bool {
    return lhs.equals(rhs: rhs) // Fix the type of the LHS using dynamic dispatch.
}
/*final*/ func !=(lhs: AnyEquatable, rhs: AnyEquatable) -> Bool {
    return !lhs.equals(rhs: rhs) // Fix the type of the LHS using dynamic dispatch.
}

class Point2D: AnyEquatable {
    let x: Double
    let y: Double
    init(x: Double, y: Double) {
        self.x = x
        self.y = y
    }
    func equals(rhs: Point2D) -> Bool {
        return x == rhs.x && y == rhs.y
    }
    func equals(rhs: AnyEquatable) -> Bool {
        guard rhs.canEqualReverseDispatch(lhs: self), let r = rhs as? Point2D else { // Fix type of RHS via a failable cast.
            return false // or fatalError("Coding Error: unequatable types; lhs: \(self), rhs: \(rhs).")
        }
        return equals(rhs: r) // LHS and RHS both Point2Ds.
    }
    func canEqualReverseDispatch(lhs: AnyEquatable) -> Bool {
        return lhs is Point2D // By default derrived types may be equal.
    }
}

let p20 = Point2D(x: 0, y: 0)
let p21 = Point2D(x: 1, y: 1)
p20 == p20 // T
p20 == p21 // F

// PointPolar can be added retrospectively (main point of technique!) and can be equal to a Point2D.
class PointPolar: Point2D {
    init(rho: Double, theta: Double) {
        super.init(x: rho * cos(theta), y: rho * sin(theta))
    }
}

let pp0 = PointPolar(rho: 0, theta: 0)
pp0 == p20 // T
p20 == pp0 // T
pp0 == p21 // F
p21 == pp0 // F

// Point3D can be added retrospectively (main point of technique!), but must be always unequal to a Point2D.
class Point3D: Point2D {
    let z: Double
    init(x: Double, y: Double, z: Double) {
        self.z = z
        super.init(x: x, y: y)
    }
    func equals(rhs: Point3D) -> Bool {
        return x == rhs.x && y == rhs.y && z == rhs.z
    }
    override func equals(rhs: AnyEquatable) -> Bool {
        guard rhs.canEqualReverseDispatch(lhs: self), let r = rhs as? Point3D else { // Fix type of RHS via a failable cast.
            return false // or fatalError("Coding Error: unequatable types; lhs: \(self), rhs: \(rhs).")
        }
        return equals(rhs: r) // LHS and RHS both Point3Ds.
    }
    override func canEqualReverseDispatch(lhs: AnyEquatable) -> Bool {
        return lhs is Point3D // Make Point3D unequal to Point2D.
    }
}

let p30 = Point3D(x: 0, y: 0, z: 0)
let p31 = Point3D(x: 1, y: 1, z: 1)
p30 == p30 // T
p30 == p31 // F

p20 == p30 // F
p30 == p20 // F
p21 == p30 // F
p30 == p21 // F
p20 == p31 // F
p31 == p20 // F
p21 == p31 // F
p31 == p21 // F

var result = ""
let ps: [AnyEquatable] = [p20, p21, pp0, p30, p31]
for po in ps {
    for pi in ps {
        result += ", \(po == pi)"
    }
}
result // TFTFF FTFFF TFTFF FFFTF FFFFT

Have tested the code better and also cross checked against “Programming in Scala”. That will teach me to post in haste.

1 Like

+1, I brought this up myself here: Dynamic equality checking, and Equatable - #2 by anandabits

I'm not against this whole effort, but please remember to take classes (and subclassing) into account when coming up with a proposal. They make it trickier than just "things that aren't the same type aren't equal".

(On the other hand, AnyHashable does something already, so maybe this is solved enough.)

2 Likes