Cons, Car, & Cdr for Tuples

While we are waiting for better generics, I am wondering if most of our problems around tuples might be solved by taking a page from the Lisp playbook (with more accessible names, of course).

Since we already have .0 which is like car, we just need something like .rest which returns a tuple minus the first element (i.e cdr), and a way to prepend a tuple to make a tuple of arity+1 (i.e cons). In addition to this, I think we should have a special protocol AnyTuple, which applies to tuples of any arity.

It leads to being able to deal with tuples inductively. (Note The generic A constrains the tuples to be the same type as each other here, even if we don't know anything else about them):

func == <A:AnyTuple> (lhs: A, rhs: A) -> Bool where A:Equatable {
    guard lhs.0 == rhs.0 else {return false} //Check that the first elements match
    return lhs.rest == rhs.rest //recursively check the rest of the tuple
    //Note: .rest will eventually return a single tuple (aka normal type) which will call a more specific implementation and end the recursion.
}

Looking at the above example, it would also be nice to be able to access the type of the first element and the type of rest. Then you could say something like: where A.0:Equatable, A.rest:Equatable which is really what we want to express.

This would probably require direct compiler support, but I think it would be worth the trouble, because it would allow us to build things like zip/unzip that work with any arity of tuple.

This is just a seed of an idea, but I think there is something useful here, which might be easier/quicker to get working than the full generics needed otherwise.

2 Likes

If I'm not mistaken, a similar approach to variadic tuples was recently put forth in this post (with further discussion in the thread). :+1:

1 Like

Aside the facts that structural types do not conform to protocols yet and there is no existential for tuples like AnyTuple, I think we might want to create view into a tuple which is indexible.

Bikeshedding:

func == <Tuple>(lhs: Tuple, rhs: Tuple) -> Bool where Tuple : AnyTuple & Equatable {
   // Creates something like `TupleSlice<Tuple>`
   let (lhsView, rhsView) = (lhs.view, rhs.view) 
   // indecies must match
   guard lhsView.indices == rhsView.indices else { return false }
   // on last index it's `() == ()` which is always true
   if lhsView.startIndex == lhsView.endIndex, rhsView.startIndex == rhsView.endIndex { 
     return true 
   }
   // extract first values and compare them (both return a value wrapped into an optional)
   guard lhsView.first == rhsView.first else { return false }
   // recursion
   return lhsView[lhsView.index(after: lhsView.startIndex)...] == rhsView[rhsView.index(after: rhsView.startIndex)...] 
}

Or we can simply iterate the indexible views, which should be even faster.

2 Likes

Oh, interesting! Thank you, I had missed this somehow.

I think the main difference is that under my proposal (A,B,C) and (A,(B,C)) would still be distinct types, so we avoid the complications from that thread. By defining a compiler provided .rest which takes (A,B,C,...) and gives you (B,C,...) we are able to work iteratively. Calling .rest on (A,B) would simply give us a value of type B, which lets us stop our recursion.

Basically there are a few bits of compiler magic needed (which we may be able to de-magic as other features come online):

  1. Compiler generates the appropriate signature/code for .rest given a tuple (e.g. (A,B,C)->(B,C) )
  2. Compiler allows the type of .0 & .rest to be checked at compile time in where clauses
  3. Magic protocol AnyTuple which all tuples (of arity > 1) inherently adhere to (we can de-magic later)
  4. Compiler generated function providing Cons functionality (e.g. (A,(B,C))->(A,B,C) )

That seems like a lot, but it should be a lot less work than would be needed for full Generics. Also, most of these seem pretty simple to me (say compared to equatable auto-generation), but I am not a compiler engineer...

A nice-to-have that I thought of later would be a generated .arity based on the type which is known at compile time, and thus can be used in where clauses like so: where A.arity == 3. I'm guessing this is trickier though, since I have never seen a number in a where clause yet. Hence, a nice to have.

1 Like