Tuples conform to Equatable, Comparable, and Hashable

Evolution Pitches
1

This is a continuation of Tuples conform to Equatable, but with Comparable and Hashable conformance! Please let me know what you think about the proposal!

Tuples Conform to Equatable, Comparable, and Hashable

Introduction

Introduce Equatable, Comparable, and Hashable conformance for all tuples whose elements are themselves Equatable, Comparable, and Hashable.

Swift-evolution thread: Tuples Conform to Equatable, Comparable, and Hashable

Motivation

Tuples in Swift currently lack the ability to conform to protocols. This has led many users to stop using tuples altogether in favor of structures that they can them conform protocols to. The shift from tuples to structures have made tuples almost feel like a second class type in the language because of them not being able to do simple operations that should just work.

Consider the following snippet of code that naively tries to use tuples for simple operations, but instead is faced with ugly errors.

let points = [(x: 128, y: 316), (x: 0, y: 0), (x: 100, y: 42)]
let origin = (x: 0, y: 0)

// error: type '(x: Int, y: Int)' cannot conform to 'Equatable';
//        only struct/enum/class types can conform to protocols
if points.contains(origin) {
  // do some serious calculations here
}

// error: type '(x: Int, y: Int)' cannot conform to 'Comparable';
//        only struct/enum/class types can conform to protocols
let sortedPoints = points.sorted()

// error: type '(x: Int, y: Int)' cannot conform to 'Hashable';
//        only struct/enum/class types can conform to protocols
let uniquePoints = Set(points)

This also creates friction when one needs to conditionally conform to a type, or if a type is just trying to get free conformance synthesis for protocols like Equatable or Hashable.

struct Restaurant {
  let name: String
  let location: (latitude: Int, longitude: Int)
}

// error: type 'Restaurant' does not conform to protocol 'Equatable'
extension Restaurant: Equatable {}

// error: type 'Restaurant' does not conform to protocol 'Hashable'
extension Restaurant: Hashable {}

These are simple and innocent examples of trying to use tuples in one's code, but currently the language lacks the means to get these examples working and prevents the user from writing this code.

After all the errors, one decides to give in and create a structure to mimic the tuple layout. From a code size perspective, creating structures to mimic each unique tuple need adds a somewhat significant amount of size to one's binary.

Proposed solution

Introduce Equatable, Comparable, and Hashable conformance for all tuples whose elements themselves conform to said protocols. While this isn't a general purpose conform any tuple to any protocol proposal, Equatable, Comparable, and Hashable are crucial protocols to conform to because it allows for all of the snippets above in Motivation to compile and run as expected along with many other standard library operations to work nicely with tuples.

Equatable

The rule is simple: if all of the tuple elements are themselves Equatable then the overall tuple itself conforms to Equatable.

// Ok, Int is Equatable thus the tuples are Equatable
(1, 2, 3) == (1, 2, 3) // true

struct EmptyStruct {}

// error: type '(EmptyStruct, Int, Int)' does not conform to protocol 'Equatable'
// note: value of type 'EmptyStruct' does not conform to protocol 'Equatable',
//       preventing conformance of '(EmptyStruct, Int, Int)' to 'Equatable'
(EmptyStruct(), 1, 2) == (EmptyStruct(), 1, 2)

It's also important to note that this conformance does not take into account the tuple labels in consideration for equality. If both tuples have the same element types, then they can be compared for equality. This mimics the current behavior of the operations introduced in SE-0015.

// We don't take into account the labels for equality.
(x: 0, y: 0) == (0, 0) // true

Comparable

Comparable conformance for tuples works just like Equatable, if all the elements themselves are Comparable, then the tuple itself is Comparable. Comparing a tuple to a tuple works elementwise:

Look at the first element, if they are equal move to the second element.
Repeat until we find elements that are not equal and compare them.

If all of the elements are equal, we cannot compare them, thus the result is false. Of course if we're using <= or >= and the tuples are exactly the same then the output would be true.

let origin = (x: 0, y: 0)
let randomPoint = (x: Int.random(in: 1 ... 10), y: Int.random(in: 1 ... 10))

// In this case, the first element of origin is 0 and the first element
// of randomPoint is somewhere between 1 and 10, so they are not equal.
// origin's element is less than randomPoint's, thus true.
print(origin < randomPoint) // true

Just like in Equatable, the comparison operations do not take tuple labels into consideration when determining comparability. This mimics the current behavior of the operations introduced in SE-0015.

// We don't take into account the labels for comparison.
(x: 0, y: 0) < (1, 0) // true

Hashable

The same rule applies to Hashable as it does for Comparable and Equatable, if all the elements are Hashable then the tuple itself is Hashable. When hashing a value of a tuple, all of the elements are combined into the hasher to produce the tuple's hash value. Now that tuples are Hashable, one can make a set of tuples or create dictionaries with tuple keys:

let points = [(x: 0, y: 0), (x: 1, y: 2), (x: 0, y: 0)]
let uniquePoints = Set(points)

// Create a grid system to hold game entities.
var grid = [(x: Int, y: Int): Entity]()

for point in uniquePoints {
    grid[point]?.move(up: 10)
}

Once again, Hashable doesn't take tuple element labels into consideration when evaluating the hash value of a tuple. Because of this, one is able to index into a set or dictionary with an unlabled tuple and retrieve elements whose keys were labeled tuples:

// We don't take into account the labels for hash value.
(x: 0, y: 0).hashValue == (0, 0).hashValue // true

grid[(x: 100, y: 200)] = Entity(name: "Pam")

print(grid[(100, 200)]) // Entity(name: "Pam")

Source compatibility

These are completely new conformances to tuples, thus source compatibilty is unaffected as they were previously not able to conform to protocols.

Effect on ABI stability

The conformances to Equatable, Comparable, and Hashable are all additive to the ABI. While at the time of writing this, there is no way to spell a new conformance to an existing type. However, these conformances are being implemented within the runtime which allows us to backward deploy these conformance to Swift 5.0, 5.1, and 5.2 clients. Because these are special conformances being added before other language features allows us to create real conformances, there is a level of runtime support needed to enable these conformances to work properly. Going forward this means we'll need to keep the entry points needed for these to work even after tuples are able to properly conform to protocols.

Alternatives considered

Besides not doing this entirely, the only alternative here is whether or not we should hold off on this before we get proper protocol conformances for tuples which allow them to conform to any protocol. Doing this now requires a lot of builtin machinery in the compiler which some may refer to as technical debt. While I agree with this statement, I don't believe we should be holding off on features like this that many are naturally reaching for until bigger and more complex proposals that allow this feature to natively exist in Swift. I also believe it is none of the user's concern for what technical debt is added to the compiler that allows them to write the Swift code that they feel comfortable writing. In any case, the technical debt to be had here should only be the changes to the runtime (or at least the symbols needed) which allow this feature to work.

Future Directions

With this change, other conformances such as Codable might make sense for tuples as well. It also makes sense to implement other conformances for other structural types in the language such as metatypes being Hashable, existentials being Equatable and Hashable, etc.

In the future when we have proper tuple extensions along with variadic generics and such, implementing these conformances for tuples will be trivial and I imagine the standard library will come with these conformances for tuples. When that happens all future usage of those conformances will use the standard library's implementation, but older clients that have been compiled with this implementation will continue using it as normal.

27 Likes
2

:tada:

3

If I understand this correctly, we would still have the following unfortunate situation, and worse:

var a = (x: 12, y: 34)
let b = (q: 12, r: 34)
print(a == b) // true
a = b // ERROR: Cannot assign value of type '(q: Int, r: Int)'
      //        to type '(x: Int, y: Int)'

That is, not only will values of different types continue to compare equal using the equality operator, they will also be equal according to their Equatable protocol conformance.

How can two values be Equatable, Hashable and Comparable when they don't even share the same type (and cannot be assigned to each other or stored in the same Set etc)?

Will this introduce the first and only case in Swift where two values of different types can be equal according to their Equatable conformance?

To make this consistent, some bigger change seems necessary, like deciding that labels are irrelevant for a tuple's type, ie that only the elements decide the type. But I guess this would be a source breaking change, since in current Swift, we have this craziness:

var c = (x: 12, y: 34)
let d = (y: 12, x: 34)
print(c == d) // true
c = d
print(c == d) // false

I'd rather see the whole tuple mess cleaned up before building more stuff on top of it.

16 Likes
4

Labelled tuples can be assigned to variable of type unlabelled tuple, so they can be though of as a subtype of unlabelled tuple. (and also a supertype, but that's not relevant) If you think of them that way, then it happens with other types already:

class Super: Equatable {
    static func == (lhs: Super, rhs: Super) -> Bool {
        true
    }
}
class A: Super { }
class B: Super { }
print(A() == B()) // true
3 Likes
5

True, thanks!

I'm still wondering about this though:

var c = (x: 12, y: 34)
let d = (y: 12, x: 34)
print(c == d) // true
c = d
print(c == d) // false

Note that if we explicitly "downcast" d to (Int, Int) prior to assignment, it will work as (perhaps most commonly) expected:

var c = (x: 12, y: 34)
let d = (y: 12, x: 34)
print(c == d) // true
c = d as (Int, Int)
print(c == d) // true
2 Likes
6

Yeah. Tuple shuffles seem like a mistake. They cause weird problems, and are not that useful.

6 Likes
7

If we added Collection for homogenous tuples, and some kind of syntax shorthand to declare them, wouldn’t it essentially give us fixed-size arrays?

Is it worth going for that now, while we can, or waiting for something like generic value parameters? Bearing in mind that we already import fixed-size arrays from C as tuples, so any FSA design that isn’t a tuple will have large source breakage.

8

(I'd like to know that too. And, as you already know, but as a convenience for others, I've an unanswered question about essentially that here.)

9

Thank you for working on this @Alejandro! I’ve wanted it for a long time and am very eager to see it happen!

I don’t think this analogy is a good one. Typically the result of comparing instances of different subclasses would be false, not true.

I don’t really have a problem with an unlabeled tuple being comparable to a labeled tuple when the types match up. But I think label shuffling is bad especially since the members are not compared labelwise. It’s even worse if two tuples with entirely different labels are comparable just because the types happen to line up.

If this is the behavior we already have with the comparison operators in concrete code this proposal certainly shouldn’t be expected to change that. But I do have some questions about how labels will be handled in generic code.

func compareValues<T: Equatable>(_ lhs: T, _rhs: T) { ... }

// Is this allowed?
compareValues((1, 2), (x: 1, 2: y))

// What about this?
compareValues((y: 1, x: 2), (x: 1, 2: y))

// What about this?
compareValues((a: 1, b: 2), (x: 1, 2: y))
4 Likes
10

Random question, shouldn‘t tuple also conform to Error when all types conform to Error as some kind of accumulator of errors which itself would be considered as an error?

11

I wouldn’t make such a sweeping generalization. Consider class clusters where there’s one public superclass, and a number of subclasses (which may or may not be public) providing specialized implementations.

It is entirely reasonable to say that two instances of the superclass (which might actually be instances of subclasses) should compare equal or unequal based solely on their salient data, not their implementation details.

1 Like
12

Yes, class clusters are an exception to that statement. Thus use of the term "typically" to soften the statement precisely so it isn't a sweeping generalization.

In any case, class clusters are certainly irrelevant to the present discussion. (x: 10, y: 10) and (a: 2, b: 2) do not have a relationship remotely like the kind seen in a class cluster. In a class inheritance analogy, they are far more similar to independent subclasses that make up part of a user-visible API surface.

2 Likes
13

Counterpoint: yes they do.

The supertype is (Int, Int), and the two subtypes do not add any stored properties, just some convenience accessors.

• • •

Regardless, as I mentioned here, I would prefer to make tuple labels have no type-system significance at all. If someone wants labels to affect type, then they should be using structs, not tuples. The labels of a tuple should exist purely for convenience.

2 Likes
14

You're only talking about the subtype / supertype relationship. This is present in all class hierarchies. Class clusters are a very particular kind of class hierarchy. Tuple labels are not just "convenience accessors". They indicate the semantics of the data contained by the tuple. Different labels imply different semantics.

I'm not sure it matters what anyone thinks about this topic now. As far as I know, changing this behavior is not on the table as it would be a significant breaking change.

15

This would provide a ton of utility. The lack of this kind of feature is one of the main reasons I don't use Tuples very often so I would love it to be available in the language!

However, my opinion on this is completely dependent on the expected timeline for generalized Tuple protocol conformance. If we're talking sometime in the next year or two, I think it makes sense to wait. Otherwise if it's more of an "eventually it will probably be added", the use case for this pitch seems valuable enough to warrant being added soon.

1 Like
16

The existence and behavior of tuple shuffles is, in my estimation, orthogonal to whether tuples conform to protocols. We already have == and < operators that take tuples, and work with labeled tuples via the existing implicit conversions, and it doesn't seem to me that making them formally Equatable and Comparable worsens the situation. And if we change the language later to reduce or eliminate these implicit conversions, then we'll get the benefits whether or not tuples have protocol conformances.

12 Likes
17

I tend to agree with this assessment. I don't see anything in this proposal which would introduce obstacles that don't already exist when it comes to evolving tuple conversions in the future.

Overall, I think this is a very well-scoped proposal. The examples from the motivation section are particularly compelling because they show how these three conformances will enable usage beyond the immediate protocol requirements (contains, dictionary keys, etc.). I'm less sure we should introduce conformances to protocols like Codable in this manner, but Equatable, Hashable, and Comparable seem like clear wins.

1 Like
18

This seems to me to be a clear case of perfect being the enemy of good. Even if the current situation with tuples is not what we'd like (and I'd suggest not using terms like "mess" and "crazy" for what seems like some fairly minor inconsistencies/inconveniences), holding back such a useful addition as this would need to be justified by examples of real harm of the interaction between the new feature and the existing deficiencies.

6 Likes
19

And to be clear, if (a: 1, b: 2) == (b: 2, a: 1) compiles, that's because the compiler is inserting an implicit conversion into the argument expressions. == would still be invoked on a single specific Equatable type in that example.

1 Like
20

This would also be the case in generic code like I posted above, correct? So it would just see (Int, Int) and the implicit conversion happens outside the generic code from the labeled to the unlabeled tuple types? If that's the case then I agree with your assessment that they're orthogonal issues.

Fwiw, I think the ideal would be to allow promotion to unlabeled tuples, but not promotion to the same unlabeled tuple type from differently labeled tuples in the same expression, as in the generic code example I posted above. i.e. the first example would work and the second two would not.

1 Like