Pair<A,B>, Nominal Tuples and Variadic Generics

I was working on a project recently and kept running into the annoying issue that, while tuples implement the equality operator, they do not implement Equatable. E.g.

struct Foo: Equatable { // error: type 'Foo' does not conform to protocol 'Equatable'
  let orderedPairs: [(String, Int)]
}

So then a naive user might try to implement the equality operator themselves:

struct Foo {
  let orderedPairs: [(String, Int)]
}

extension Foo: Equatable {
  static func == (lhs: Foo, rhs: Foo) -> Bool {
    return lhs.orderedPairs == rhs.orderedPairs // '<Self where Self : Equatable> (Self.Type) -> (Self, Self) -> Bool' requires that '(String, Int)' conform to 'Equatable'
  }
}

"What the hell!?" they think, "String is Equatable. Int is Equatable. But (String, Int) is not Equatable? But I can compare tuples right?" So they try again.

struct Foo {
  let orderedPairs: [(String, Int)]
}

extension Foo: Equatable {
  static func == (lhs: Foo, rhs: Foo) -> Bool {
    return zip(lhs.orderedPairs, rhs.orderedPairs).lazy
      .contains { $0 != $1 }
  }
}

Finally, it works. They don't really understand why they had to jump through all these hoops and they're annoyed. Also, if the ordered pairs were a member of a much larger struct, they would have to implement a complex equality operator just to add this one field. So they try to build a reusable component.

struct Pair<A, B> {
  let first: A
  let second: B
}

extension Pair: Equatable where A: Equatable, B: Equatable {
  static func == (lhs: Pair<A, B>, rhs: Pair<A, B>) -> Bool {
    return lhs.first == rhs.first && lhs.second == rhs.second
  }
}

struct Foo: Equatable {
  let orderedPairs: [Pair<String, Int>]
  ...
}

This works well enough until they want to add more elements to the tuple. At this point they could continue making more strictly typed objects, (maybe using a meta programming library like Sourcery), or they could make one object which type-erases the tuple which isn't great either.

All of these issues could be solved with Variadic Generics and a nominal Tuple type on which we could write a conditional conformance to Equatable. While I know Variadic Generics were a part of the Generics Manifesto, I was told that they're not a priority at the moment, and will likely come after ABI stability is established. I feel like this is a mistake. The language does not feel fully formed without them. Most functional programming libraries like Prelude are forced to either result to runtime hackery, or they codegen generic function overloads up to some arbitrary arity (e.g. you can curry functions of up to 4 arguments). For a language that supposedly supports FP as a first class programming paradigm, the lack of variadic generics feels like a major letdown.

In the event that we don't see Variadic Generics anytime soon, I think we need better solutions in place for working with Tuples and functions of many arguments. I'm definitely open to suggestions here, but I was thinking that at least for the time being we could make tuple a nominal type and add an Equatable conformance as a workaround in the meantime (like Array had before conditional conformances). What do you think?

5 Likes

This has come up a handful of times on the forum; it's well-understood that folks want this and are aware of the problem, and there's some detailed discussion here: Synthesizing Equatable, Hashable, and Comparable for tuple types

How would this work? Since a nominal type has to have a name, without variadic generics, you'd need a different name for each arity because they have to be distinct types. Would you have Tuple2<A, B>, Tuple3<A, B, C>, and so forth?

That's the thing—Array didn't have Equatable conformance before conditional conformance. There was no workaround; it implemented the == operator but it still could not be used in a context where you needed something that conformed specifically to Equatable, which is what it sounds like you want here. The way tuples support equality today is effectively already how arrays did it before conditional conformance.

There's some debate in the thread I linked about whether making existing non-nominal types like tuples nominal types is the right thing to do. It's also noted in a reply by @Douglas_Gregor that this could be designed and implemented without requiring tuples to become nominal types.

For what it's worth, I did some experimentation a while back in the ProtocolConformance machinery in the compiler to see how much work it would be to fit tuples into the model. It got ugly really fast; that class hierarchy has some pretty strong assumptions that you always have a root nominal conformance that you can work with, and trying to ease that restriction cascaded through a lot of other parts of the implementation. It was unfortunately beyond the knowledge level and bandwidth that I had at the time (and probably have now).

I'd love to see someone figure out how to make it work, though. Fewer special cases in the language == better.

1 Like

Yes, precisely. Unfortunately without Variadic Generics, afaik we don't have any better options. At least until we do, I'd want tuples up to N=8 (?) elements to have nominal (albeit internal) types that conform to Equatable, Hashable and Comparable with conditional conformances.

Sorry, I misspoke. I meant the synthesized Codable conformance. IIRC in Swift 4.0 Set, Array and Dictionary implemented Codable even though there were cases where it could trap because it didn't have a way to ensure that its elements were also Codable.

We could essentially have tuples "lie" and say they're equatable. Assuming there was an internal, nominal tuple type, it could implement Equatable and then call the special case == implementation. If the type signatures, order, or length of two tuples don't match up return false. Otherwise compare each element. Codable would do the same thing Array did before - lie and trap if you have a non-codable element.

Here's a salient post from @Joe_Groff:

I think we all agree that this would be a good idea; no nominal types are required. The limiting factor isn't the idea but someone implementing it.

6 Likes

Not necessarily.

struct Void {
  init() {}
}
struct Tuple<First, Rest> {
  var first: First
  var rest: Rest
}

Then make () sugar for Void, (T, U) sugar for Tuple<T, U>, (T, U, V) sugar for Tuple<T, Tuple<U, V>>, etc. This design lends itself to recursive definitions of protocol conformances:

extension Void: Equatable {
  static func == (lhs: Void, rhs: Void) -> Bool {
    return true
  }
}
extension Tuple: Equatable where First: Equatable, Rest: Equatable {
  static func == (lhs: Tuple, rhs: Tuple) -> Bool {
    return lhs.first == rhs.first && lhs.rest == rhs.rest
  }
}
7 Likes

Nice! That's a unique approach that hadn't occurred to me and it does compose nicely with the protocols.

Given the work it would take to make the new type compile down to the same ABI as existing tuples, along with adding a type to stdlib that it would have to live with for a while, I hope someone would spend the effort just implementing conformances on non-nominal types instead :slightly_smiling_face:

1 Like

Except that would mean (T, U, V) == (T, (U, V)) because (T, U, V) == Tuple<T, Tuple<U, V>>, but (T, (U, V)) == Tuple<T, W> where W == Tuple<U, V>.

They are 'binary equivalent', but I don't think they should be 'equal'.

1 Like

Yeah, that’s true. The solution would be to represent 2-tuples as Tuple<T, Tuple<U, Void>> (and constrain Rest to a TupleProtocol that only Tuple and Void conform to), but that means 1-tuples are now a real thing we need to grapple with. Maybe the type checker just needs to freely and automatically cast Tuple<T, Void> to T, though.

1 Like

If you do that, then you’re back at where you started in terms of (T, U, V) and (T, (U, V)).

I've read many requests for variadic generics, but no convincing concept how they should be implemented...

Although I think it should be possible to extend tuples, I don't think this is a pattern that should be used often:
When you need an entity in many places, and behavior for that entity, it most likely also deserves a name - and that's what a struct offers.

1 Like

I think instead that they should be equal. The only semantic content of a tuple type is "these are the types, and this is the order", so (A,(B,C)) has the same semantic content of (other than being isomorphic to, of course) (A,B,C), and as far as I know many languages actually internally represent a 3-type tuple with 2 nested 2-type tuples.

I talked about this at long in a old discussion about SE-110.

2 Likes

So what you are saying is that tuples should not be nestable,
ie tuples should not be allowed within tuples,
ie a tuple type should be a list of any types except tuple types (and Void is a special-case which disappears from the list, according to your posts in the other thread)?

When you say:

I could say that for the tuple type (A, (B, C)), these are the types and this is the order:
1st type: A
2nd type: (B, C)

But if (A, (B, C)) should be equivalent to (A, B, C), then (B, C) would have to be considered not a type. So tuple types should not be types?

I've said a lot about this in the past but there is a significant region of use cases where tuples make more sense than structs – read: points, vectors, quaternions, etc. structs should only be used when there is "creativity" in structure layout

1 Like

Scala defines Tuple0, Tuble1<T0>, ..., Tuple22<T0, ..., T21>, which is a simple solution and works well in practice.

But does it? It seems to give problems in type inference. Also, a Variadic (or a Value-typed one) generics system would allow you to declare things like these:

Tuple<T, i: UInt>, Vector<T: Field, i: UInt>

And make dimensionality checks at compile-time rather than at runtime.

Edit: fixed a typo. Also:

A variadic system would read differently, but would allow (albeit with maybe not so clear syntax) to do the same thing.

I'd would only treat as compilation error something like let x = ("hi",(),42), that is, I wouldn't allow to write () within a tuple (() is meaningless, and can be grabbed out of thin air if you somehow "need" it), including (()), or assigning it to a variable: let y = () is meaningless, and should be a compilation error.

In other cases, when assigning a tuple to a variable or returning it from a function, I'd like the compiler to automatically flatten the tuple type. For example:

func getIntAndString() -> (Int,String) { /* some implementation */ }

let x = (true, getIntAndString()) /// the type of this should be (Bool, Int, String)

Of course they should, I would also say that tuples should be treated as nominal types (hence, extendable), but only flattened. In your example, (B,C) would not be considered a type if within another tuple, because the resulting tuple would be flattened automatically.

(A,B,C) and (A,(B,C)) have the same information, are completely isomorphic, literally tell the same thing.

This approach would completely eliminate "problems" generated by the the impossibility of destructuring nested closure arguments (because there would only be a flattened collection of arguments), making it also easier to call higher-order functions in a point-free style.

Hello, I don't get it. Imagine a function that takes a (B, C) argument. It's trivial to extract it from (A, (B, C)): tuple.1. However, how do I extract it from a flattened (A, B, C)? I mean, one can't really discuss internal compiler implementation without talking developers' daily job eventually, or am I mistaken?

4 Likes

Wouldn't you be able to pass (tuple.1, tuple.2), or am I missing something?

Not sure what the problem is here.

In the context of a closure, what you really want in general is to destructure tuple arguments. If all tuples were flattened, a (A,(B,C)) would be converted in (A,B,C), so in a closure you would use something like { _, this, that in ... }, and then call a function f(tuple:) like this f(tuple: (this, that)). But in this case, I would review for a second why you wrote a function that takes a single tuple argument, instead of two separate arguments.

I actually am discussing developer's convenience, really. I don't know if flattening tuples would be impossibile at the compiler lever, but it would be more convenient for the developer.

As I wrote, I personally am not such a big fan of using tuples for anything aside ad-hoc return values - but I think there's quite a difference between

typealias DirectedForce = (force: Float, direction: (Float, Float, Float))
...
print("Direction: \(f.direction)")

and

typealias DirectedForce = (Float, Float, Float, Float)
...
print("Direction: \(f.1), \(f.2), \(f.3),")
3 Likes