Implementing apply on tuples in Scala

Posted on September 1, 2017

One of the first things you learn as a newcomer to Scala is the difference between a list and a tuple: a list must be homogeneous but a tuple can be heterogeneous. That is all elements of a list must have the same types but a tuple can contain things of different types.

A direct consequence of this is that a list can define a by-index accessor and a tuple cannot. You can use list(3) but you can’t do tuple(3) - you need to do tuple._4 (and there is that pesky off-by-one).

So let’s use the awesome powers of Scala to negate this and implement apply method on tuples.

First steps

Let’s start with with baby steps and not tackle full blown apply with integer index but instead do an approximation with special access constants. Something like

It’s not a big step from regular tuple accessors but it’s a big move since it introduces a single polymorphic apply.

To pull this off we’ll type classes in conjunction with singleton types. The apply will take in one of the singletons and use implicit resolution to pull in the function that does the proper projection. The important part is that the implicit resolution also needs to compute the output type of the apply method.

The type-class needs to correlate the tuple type (T), the output type (A) and the index (N). The instances just implement the obvious connection between indexes and tuple accessors.

If you haven’t seen types like _1.type before: this is precisely the type of the value _1. Only its exact copies can inhabit it at any time.

Now we can write the extension apply method that uses this mechanism.

And it will work. But you need to use _1 instead of regular 1 to give the implicit resolution mechanism sufficient clues. Not pretty enough.

Enter Nats

To integrate deeper with the language we need to lift the integers into the type level somehow.

Since I don’t feel like writing 22 instances let’s start off with unary encoding.

And a corresponding value level representation that also keeps the type around with an implicit conversion from integers so this is all auto-magical.

The trick here is the type member that is defined to match the number itself. This way the type checker gets access to the “value. Now we just need to rewrite the instances to use this.

Except it doesn’t work. This mechanism will generate the Nats but it’s too weak - N will just be n.N and this is not enough information to power implicit resolution. If only there was a way to fully generate the types at compile time…

Macros to the rescue

We can keep the Nat type and the implicit conversion into it but implement it as a macro that just generates TNats directly (without recursion). This will give strong enough types to power implicit resolution.

Now we can rewrite the instances.

And it works!

Simplifying

Since we already have a macro sitting in there why not have it do all the heavy lifting? We can cut bulk of the code and remove a lot of the complexity of the implicits if we just use a macro that transforms a.apply(n) into a._${n + 1}.

This works but I think it’s not the best idea. See, macros don’t compose. You cannot really use this from another function, you always need to statically know the index. As where with the previous implementation you are good to go as long as you have a good Nat and the At instance. Which you can pass in programmatically. And you just push the implicit conversion to Nat a layer out. This way you can re-use the indexing mechanism for other operations and you just have a single macro sitting in the background powering things instead of having a bunch of one-offs.

In fact this is exactly what shapeless already does! It uses very similar ideas and pushes them much further. But most importantly, it already includes our apply so if you actually want to do this just import shapeless.

Facebook Twitter Google Digg Reddit LinkedIn StumbleUpon Email
comments powered by Disqus