Tuples conform to Equatable

Imho adding conformances for tuples is a good idea, but I wish there was a bigger plan what should happen in the long run, instead of allowing some basic protocols in an ad hoc fashion.

  • Will tuple conformance always stay a special-case feature?
  • Will it be limited to protocols that only define operators (and some special cases)?
  • Or are we going to see extension (Int, Int): SomeProtocol in the future?

I can't see any downsides for the last option, as it fits great into my model of tuples as anonymous structs - but I know that for every possible change, you can find someone who opposes ;-)

Thinking about this, I might have found a downside myself ;-): When you allow custom conformances, you can have incompatible implementations - this does not happen when everything is handled by the compiler. But the same problem already exists for other types, so imho that's not a dealbreaker. It's still worse for tuples, though...

4 Likes

Not quite true, depending on what exactly we mean by "different labels". This little program shows what I mean, and more (this is current behavior in Swift 5.1):

var a = (x: 2, y: 4)
var b = (y: 4, x: 2)

print(a.x == b.x && a.y == b.y) // true
print(     a     ==     b     ) // false

a = b         // <-- Assigning despite `a` and `b` having different labels.
print(a == b) // false
b = a         // <-- Assigning despite `b` and `a` having different labels.
print(a == b) // false

: O

Those assignment are allowed because of an accepts-invalid bug, right?

Expected behavior: The labels of a should be considered different from the labels of b, because tuple element order matters, and thus the assignment should be an error.

Observed behavior: The labels of a are considered the same as the labels of b, as if tuple element order didn't matter, and thus the compiler accepts invalid code.

( Filed SR-12112 )

4 Likes

Is there really an obvious (and mandatory, non-customizable) Comparable-conformance that would make sense for eg these:

let person = (firstName: "Ada", lastName: "Lovelace", birthDate: Date(/*...*/))
let coordinate = (latitude: 40.689263, longitude: -74.044505)
let dmy = (day: 30, month: 1, year: 2020)
let ymd = (year: 2020, month: 1, day: 30)  

?

If so, I assume that the same Comparable conformance will be automatically synthesized for struct, ie that the following will compile in a future version of Swift:

struct ImperialMeasure : Hashable, Comparable { // Error (currently, because of Comparable)
    var inches: Double
    var feet: Double
    var yards: Double
    var miles: Double
}

I couldn't come up with a less contrived (and stupidly designed) type, but you get the idea: The order of the stored properties would make or break measureA < measureB semantically (something which is not the case for measureA == measureB and hashing).

What I'm trying to say is that while needing to write custom Equatable (and Hashable) conformances is not uncommon (there are cases where the automatically synthesized conformances won't make sense), it would probably be much more common for Comparable, perhaps even so common that it would be better to leave it as it is (ie no automatically synthesized Comparable conformances). And if so, that would probably mean that there is no obvious Comparable conformance that makes enough sense for all tuples to be worth its weight (in potential confusion etc) either.

Sorry if all of this has already been discussed or clarified elsewhere.

1 Like

Tuples already support lexicographic comparison. This pitch just makes that available as a Comparable conformance.

That would need to be a standalone pitch. The issue here is that the synthesized Comparable conformance would depend on source order and would change if the source is edited and the properties change order. My guess is there would be a heated debate over whether this is acceptable or not.

4 Likes

Unrelated, but I hate that those conversions are allowed. They can cause surprising performance cliffs.

1 Like

It is a fairly significant limitation of the language today that structural types flat out do not support protocol conformance today, and it is a language change to break that assumption. I wouldn't personally expect much contention from the high-order idea that tuples have these protocol conformances, but adding them as a special case does have interactions with future language directions (allowing structural types to conform to protocols, variadics, and such) that need to be considered, and for some conformances like Codable, there are design decisions to be made about what the behavior should be.

5 Likes

I think there probably ought to be a proposal and review for this change, but to play devil's advocate, SE-0015 arguably already proposed this change and was accepted:

The Swift standard library should provide generic implementations of the comparison operators for all tuples up to some specific arity. The arity should be chosen so as to balance convenience (all tuples support this) and code size (every definition adds to the size of the standard library).

When Swift gains support for conditional conformation to protocols, and if Swift ever gains support for extending tuples, then the tuples up to the chosen arity should also be conditionally declared as conforming to Equatable and Comparable .

If Swift ever gains support for variadic type parameters, then we should investigate redefining the operators (and protocol conformance) in terms of variadic types, assuming there's no serious codesize issues.

The "some specific arity" just happens to be infinite. :^)


Yes—lexicographic comparison from left to right. SE-0015 already added overloads of < and friends to implement precisely this behavior for tuples of 1-6 elements; they just aren't formally modeled as a Comparable conformance.

This was discussed in SE-0185:

The original discussion thread also included Comparable as a candidate for automatic generation. Unlike equatability and hashability, however, comparability requires an ordering among the members being compared. Automatically using the definition order here might be too surprising for users, but worse, it also means that reordering properties in the source code changes the code's behavior at runtime.

This logic doesn't apply to tuples because reordering tuple elements can, and often does, break use sites; reordering properties usually doesn't.

This is a a discussion we could reopen, of course, but it's a pretty distinct discussion from tuple conformances; I don't think we should try to have both simultaneously.

8 Likes

Actually you can do much better than that. Let's first view a protocol as a type, and pretend we have subtyping. Then there's a standard rule, that product types are covariant, variant types (enums in Swift) are covariant, and function types are contravariant in their domain and covariant in their codomain.

Its unfortunate swift pretends functions can have multiple arguments instead of just relying on tuples, but lets ignore that.

So in summary, subtyping is actually quite easy to support for structural types such as tuples. Its actually nominal subtypes that are hard (because they require table lookups to decide if X is a subtype of Y).

So now what we can say is that if we have a subtyping relation, including considering that a type T conforming to a protocol P might hold, then that relation also holds for tuples on a component by component basis.

The real question is: why waste time on a proposal that ONLY extends tuples with a small fixed set of such relations such as Equatable, Hashable, etc, instead of all of them. The implementation in the unification engine is trivial.

Indeed given extensible variants (enums), they too support covariant subtyping on both a width and depth basis. Actually tuples support width subtyping too but it is likely to be very confusing losing the tails of tuples accidentally.

Also: MutableCollection & RandomAccessCollection for homogeneous tuples? Such as those imported from C fixed-size arrays.

  • An unkeyed container for a tuple with fully unlabelled elements?
    e.g. (123, 456) encoded in JSON as [123, 456]

  • A keyed container for a tuple with fully labelled elements?
    e.g. (x: 123, y: 456) encoded in JSON as {"x": 123, "y": 456}

  • Which container for a tuple with partially labelled elements?
    e.g. (123, z: 456) encoded in JSON as [123, 456] or {"0": 123, "z": 456}

I think that would also be interesting to consider. It too would probably deserve a design discussion and proposal of its own.

2 Likes

Swift used to pretend functions take a single argument (which might be a tuple) and this caused no end of trouble. It's a nice model in some languages, but not a good fit for Swift, for various reasons:

  • default arguments
  • variadic arguments
  • inout arguments
  • generic substitution (eg, Array<T>.append(_: T) with T a tuple type)

The new model was a conscious change that required a fair amount of work to plumb through but the result was a simpler and more internally consistent language model and implementation.

12 Likes

Interesting. Felix has single argument functions. It also has default arguments, variadic arguments, and supports a way to do input/output (differently). Functions cannot have multiple arguments, so what you actually have is that each function is a combination of a function that takes a single argument underneath, and an N-functor to construct it. This creates no end of problems generalising higher operations. With tuples the higher operations are isolated to the sole N-functor which creates a tuple. C++ has the same problem. So does Rust.

For example, function composition is trivial if you only allow one argument. It's impossible if you have two arguments, because no function can return two arguments, only a tuple. So you actually have to map a function of two arguments to one which has only a tuple first, before doing the composition, and you need a different map for every number of arguments to be general.

In any case its too late to fix. I agree, tuples should support equality. And they should also support quite a lot of other protocols. My primary concern with the proposal is that it doesn't go far enough. It would be better if the language could be extended, so that the specialisation of a protocol to tuples could be written in the language, rather than a few select ones being implemented in the compiler.

In Felix, user code provides equality, total ordering, and conversion to string for all tuples. The way this is done is to provide a second model of tuples similar to that used for lists: a head and tail representation. This allows polymorphic recursion to process a tuple of arbitrary length. In Felix the result type must be invariant. I think you need GADTS otherwise, which Felix has, but are hard to work with. The main problem is .. well .. it won't work for functions that take a list of arguments. So another feature needs to be added, to normalise function representation using a list of arguments back to using a tuple, and then one to unpack the tuple back to a list.

Hash is different. A tuple hash isn't a combination of component hashes. For hashing, any object represented in a contiguous sequence of bytes can be hashed by hashing the byte sequence. So a tuple of value types can be hashed, even if the component value types can't. So this problem could be solved by simply saying all value types are hashable. Stuff gets hard when you have pointers in there.

Here is Felix code, in the library, which provides equality. I will explain below the code. Swift could do this too with the right enhancements, and do it simpler for a reason to be explained.

instance [T,U with Eq[T], Eq[U]] Eq[T ** U] {
  fun == : (T ** U) * (T ** U) -> bool =
  | (ah ,, at) , (bh ,, bt) => ah == bh and at == bt;
  ;
}

instance[t,u with Eq[t],Eq[u]] Eq[t*u] {
  fun == : (t * u) * (t * u) -> bool =
  | (x1,y1),(x2,y2) => x1==x2 and y1 == y2
  ;
}

instance[t with Eq[t]] Eq[t*t] {
  fun == : (t * t) * (t * t) -> bool =
  | (x1,y1),(x2,y2) => x1==x2 and y1 == y2
  ;
}

So here's the explanation. First, the type A * B * C etc is the type of a tuple. The cartesian product is an N-ary operator, not a binary operator. However there is a second type for a tuple, written with two stars. A ** B * C, and ** is a right associative binary operator. Values can be written in the form (1,,"hello",,X) for example, where X is a tuple. There's a Felix specific gotcha: in Felix there are no tuples of one component. Three instances are required because of this. In Swift, you only need two, one to handle the recursion, and one to handle the base case, the unit tuple ().

An instance is an implementation of a protocol (type class in Haskell, class in Felix). The functions use a pattern match in Ocaml/ML style. So the rule for equality is given by:

  | (ah ,, at) , (bh ,, bt) => ah == bh and at == bt;

which simply reads, two tuples a and b are equal is the head components are equal and the tail is equal. The "with" clause is Haskell and Swift "where" clause.

Just to reinforce it, the recursion for less than is given by:

instance [T,U with Tord[T], Tord[U]] Tord[T ** U] {
  fun < : (T ** U) * (T ** U) -> bool =
  | (ah ,, at) , (bh ,, bt) => ah < bh or ah == bh and at < bt;
  ;
}

This is user code in the library. The primary requirement is that tuples have a recursive representation. One also needs polymorphic recursion to be unrolled during monomorphisation.

Anyhow the point is that this can be done for any function whose codomain is in variant. In other words a function T -> X where T is generic and X is fixed, can be extended to a tuple by unpacking the tuple into a head and tail, applying the function to the head, and then folding that into the function applied to the tail. Its a boilerplate, in which the folding is the part the user has to write. The fold for equality is just logical conjunction, for less than the fold is a bit harder.

Getting this to work in Swift is a lot more ambitious than just adding equality for tuples. The plus side is that it allows the user to make tuples conform to protocols they invented themselves, which the library or compiler can obviously never do.

Conversion to JSON:

(123,456,x:789,a:42) --> {0:123, 2:456,"a":42,"x"789}

Uniform and complete. Use index for unlabelled components, string labels for labelled ones, put the numeric ones first, and sort the labelled ones alphabetically.

unfortunately JSON keys have to be strings

(123,456,x:789,a:42) --> {"_0":123, "_1":456,"a":42,"x"789}

Assuming _1 etc are not legal swift labels. Or some modification. One can pretend I think swift "tuples" are actually records, with the unlabelled components labelled implicitly with integers. So if r=(1,x:2) then r.0 and r.x already work, yes? So actually, they're not tuples they're records. Unfortunately that makes my decomposition by polymorphic recursion fail. Generalising to records requires introducing label variables and other really advanced stuff. Hmm.

There are formatting options in JSONEncoder.OutputFormatting but they would be chosen by the user:

let encoder = JSONEncoder()
encoder.outputFormatting = [.sortedKeys]

The choice for the compiler is which container to use from the Decoder and Encoder.


Using an unkeyed container for all tuples, regardless of element labelling, would be the simplest choice:

// `Codable` conformance synthesized by the compiler for any of
// `(Int, Int)` or `(x: Int, y: Int)` or `(Int, z: Int)` tuples.

init(from decoder: Decoder) throws {
  var unkeyedContainer = try decoder.unkeyedContainer()
  tuple = (
    try unkeyedContainer.decode(Int.self),
    try unkeyedContainer.decode(Int.self)
  )
}

func encode(to encoder: Encoder) throws {
  var unkeyedContainer = encoder.unkeyedContainer()
  try unkeyedContainer.encode(tuple.0)
  try unkeyedContainer.encode(tuple.1)
}

But it might be useful, when decoding some JSON containing {"x": 123, "y": 456}, to be able to use a tuple instead of a struct.

In which case, the compiler could choose a keyed container for a tuple with fully (or partially?) labelled elements:

// `Codable` conformance synthesized by the compiler for the
// `(x: Int, y: Int)` tuple.

enum _TupleCodingKeys: String, CodingKey {
  case x
  case y
}

init(from decoder: Decoder) throws {
  let keyedContainer = try decoder.container(keyedBy: _TupleCodingKeys.self)
  tuple = (
    x: try keyedContainer.decode(Int.self, forKey: _TupleCodingKeys.x),
    y: try keyedContainer.decode(Int.self, forKey: _TupleCodingKeys.y)
  )
}

func encode(to encoder: Encoder) throws {
  var keyedContainer = encoder.container(keyedBy: _TupleCodingKeys.self)
  try keyedContainer.encode(tuple.x, forKey: _TupleCodingKeys.x)
  try keyedContainer.encode(tuple.y, forKey: _TupleCodingKeys.y)
}

For your (123,456,x:789,a:42) example, the string keys can be "0" and "1" for the unlabelled elements:

enum _TupleCodingKeys: String, CodingKey {
  case _0 = "0"
  case _1 = "1"
  case _2 = "x"
  case _3 = "a"
}

The enum would be private to the compiler, and the user wouldn't be able to customize tuple coding by providing their own CodingKeys enum.

Right. The important thing is that distinct tuples produce distinct JSON. But I tried elsewhere to suggest maybe the user could control it, no need for the compiler to be involved. However, my method only works for actual tuples, Swift "tuples" allow labels which are part of the type, yes? That's too hard to support with a language extension so it would be necessary then to have the compiler do it.

You said:

Using an unkeyed container for all tuples, 
regardless of element labelling, 
would be the simplest choice:

and of course that's correct, except: how do you order the labelled components?
According to this:

func ff(p:(x:Int,y:Int)) { print(p.x,p.y,p.0,p.1);}
ff (p:(x:1,y:2))
ff (p:(y:2,x:1))
ff (p(1,2))

there's no order for labelled components (that's as close to an equality test as I could do). I have to guess what the types are here. I'm guessing (1,2) converts to (x:1,y:2) to call the function. On the other hand the first two argument are exactly the parameter type. In this case, the conversion in the third call is incoherent, in the sense that, the same argument, if the parameter labels are swapped, will have different semantics even though the parameter type is the same. i must be missing something (because if I'm not the type system is unsound).

Swift already has some magic to support something like this, methinks.
If you e.g. have a collection of tuples, you can call .map on it with a function that takes two arguments.

Not necessarily. The element labels will be ignored for synthesized Equatable:

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 types, then they can be compared for equality.

I imagine synthesized Codable would be much simpler by ignoring element labels (i.e. using an unkeyed container).

And it would be consistent with the compact encoding chosen for Range, ClosedRange, etc.

1 Like