Why is the Aux technique required for type-level computations?

There are two separate questions here:

1. Why does Shapeless use type members instead of type parameters in some cases in some type classes?
2. Why does Shapeless include Aux type aliases in the companion objects of these type classes?

I’ll start with the second question because the answer is more straightforward: the Aux type aliases are entirely a syntactic convenience. You don’t ever have to use them. For example, suppose we want to write a method that will only compile when called with two hlists that have the same length:

import shapeless._, ops.hlist.Length

def sameLength[A <: HList, B <: HList, N <: Nat](a: A, b: B)(implicit
  al: Length.Aux[A, N],
  bl: Length.Aux[B, N]
) = ()

The Length type class has one type parameter (for the HList type) and one type member (for the Nat). The Length.Aux syntax makes it relatively easy to refer to the Nat type member in the implicit parameter list, but it’s just a convenience—the following is exactly equivalent:

def sameLength[A <: HList, B <: HList, N <: Nat](a: A, b: B)(implicit
  al: Length[A] { type Out = N },
  bl: Length[B] { type Out = N }
) = ()

The Aux version has a couple of advantages over writing out the type refinements in this way: it’s less noisy, and it doesn’t require us to remember the name of the type member. These are purely ergonomic issues, though—the Aux aliases make our code a little easier to read and write, but they don’t change what we can or can’t do with the code in any meaningful way.

The answer to the first question is a little more complex. In many cases, including my sameLength, there’s no advantage to Out being a type member instead of a type parameter. Because Scala doesn’t allow multiple implicit parameter sections, we need N to be a type parameter for our method if we want to verify that the two Length instances have the same Out type. At that point, the Out on Length might as well be a type parameter (at least from our perspective as the authors of sameLength).

In other cases, though, we can take advantage of the fact that Shapeless sometimes (I’ll talk about specifically where in a moment) uses type members instead of type parameters. For example, suppose we want to write a method that will return a function that will convert a specified case class type into an HList:

def converter[A](implicit gen: Generic[A]): A => gen.Repr = a => gen.to(a)

Now we can use it like this:

case class Foo(i: Int, s: String)

val fooToHList = converter[Foo]

And we’ll get a nice Foo => Int :: String :: HNil. If Generic‘s Repr were a type parameter instead of a type member, we’d have to write something like this instead:

// Doesn't compile
def converter[A, R](implicit gen: Generic[A, R]): A => R = a => gen.to(a)

Scala doesn’t support partial application of type parameters, so every time we call this (hypothetical) method we’d have to specify both type parameters since we want to specify A:

val fooToHList = converter[Foo, Int :: String :: HNil]

This makes it basically worthless, since the whole point was to let the generic machinery figure out the representation.

In general, whenever a type is uniquely determined by a type class’s other parameters, Shapeless will make it a type member instead of a type parameter. Every case class has a single generic representation, so Generic has one type parameter (for the case class type) and one type member (for the representation type); every HList has a single length, so Length has one type parameter and one type member, etc.

Making uniquely-determined types type members instead of type parameters means that if we want to use them only as path-dependent types (as in the first converter above), we can, but if we want to use them as if they were type parameters, we can always either write out the type refinement (or the syntactically nicer Aux version). If Shapeless made these types type parameters from the beginning, it wouldn’t be possible to go in the opposite direction.

As a side note, this relationship between a type class’s type “parameters” (I’m using quotation marks since they may not be parameters in the literal Scala sense) is called a “functional dependency” in languages like Haskell, but you shouldn’t feel like you need to understand anything about functional dependencies in Haskell to get what’s going on in Shapeless.