Scala 3 Enlightenment — Type Matching against Tuple

Coauthor: Ying Xiong

Scala 3 provides a myriad of metaprogramming features that are insanely empowering, elegant, and addictive. For the uninitiated, however, these features may not feel that way. In fact, some of them might appear befuddling or outright mystic. Looking back at our journey to enlightenment, we realized that it’s helpful to start with features in a certain order, one small step at a time. For this installment, we will experiment with Tuple and type matching.

Tuple is a data structure that is similar to List in many aspects. The matrix below highlights some relevant similarities between the two recursive structures.

            Tuple                          List
empty       EmptyTuple                     Nil
non-empty   head *: tail (tail is Tuple)   head :: tail (tail is List)

Tuple can be constructed in a similar fashion:

val t0: Tuple = EmptyTuple                    
val t1: Tuple = 1 *: EmptyTuple               
val t2: Tuple = true *: "hello" *: EmptyTuple

Tuple can also be pattern matched:

val firstElementIsTrue: Boolean = t2 match {
    case true *: _ *: EmptyTuple => true
    case _ => false
}

There is, however, an essential difference between Tuple and List: only Tuple supports type matching, a feature which is fairly accessible and tremendously powerful. For a road test, let’s fire up a Scala command line console for a thought game, “Type Nazi”.

The rule of the game is to code at the type level. Any computation can only use types and return the result as a type alias. What this rule entails is that one can not create variables using the val or var modifier, because such variables are value level constructs.

First, create a Tuple consisting of types and assigns it to an alias using the type modifier:

type T = Float *: Char *: EmptyTuple

The Scala console responds with the following:
// defined alias type T = Float *: Char *: EmptyTuple

Second, find out the last element in T via type matching:

type LAST = T match {
     case _ *: last *: EmptyTuple => last
     case _ => Nothing
}

The console displays the expected type for LAST:
// defined alias type LAST = Char

Therefore, type matching is a cousin of value level pattern matching. Within a match branch, one can assign a type variable to an element of interest. In this case, `last` is a type variable to the last element of the Tuple.

What’s fascinating about type matching is that it can be recursive.

type LAST[X <: Tuple] = X match {
     case EmptyTuple => Nothing
     case last *: EmptyTuple => last
     case _ *: tail => LAST[tail]
}

This time, the type alias takes a type parameter X that extends Tuple. Notice that type level recursion works the same way as its value level counterpart. If X starts as EmptyTuple, the result will be of type Nothing. During each iteration against the tail, the length of X will be decreased by one until there is only one element left.

The recursive type matching above is not directly executable, because a parameterized type behaves like a type level function. To “call” it, one has to feed it the expected type parameter, using the square bracket syntax, [X]. Below is an example to invoke the parameterized type alias.

type VERIFY = LAST[EmptyTuple]

The compiler reports that the last element of EmptyTuple is, Nothing.
// defined alias type VERIFY = Nothing

Another test case:

type VERIFY = LAST[Float *: Double *: String *: Int *: EmptyTuple]

Running the VERIFY code generates the following expected result:
// defined alias type VERIFY = Int

Try to convince ourselves that List is not qualified for the game:

type T = Float :: Char :: Nil

The compiler throws a tantrum:

-- [E023] Syntax Error: ----------------------------------------
1 |type T = Float :: Char :: Nil
  |         ^^^^^^^^^^^^^^^^^^^^
  |         Too many type arguments for ::[A]
  |         expected: [A]
  |         actual:   [Float, Char :: Nil]

It shall be clear now that List works at the value level. It doesn’t have the type level mojo.

To summarize, this introduction discusses austerely beautiful properties of Tuple and type matching. Tuple can be constructed with values or types and pattern matched at the value or type level, respectively. It’s a heterogeneous list that faithfully keeps concrete element types. Furthermore, type matching can be done recursively against parameterized types.