Scala 3: Type Lambdas, Polymorphic Function Types, and Dependent Function Types

Type lambdas are the type analog of “value lambdas”, also known as functions 🤓. This post explores them. The discussion naturally leads to the new ability to parameterize the types of functions, which was previously only supported for methods. While I’m at it, I’ll mention another method feature that’s now supported for functions, dependent function types.

March 8, 2021: Updated the Functor example after helpful feedback from Sergei Winitzki.

Sofitel in the Snow, ©2021, Dean Wampler, All Rights Reserved

You can start reading the rough draft of Programming Scala, Third Edition on the O’Reilly Learning Platform. Most of the chapters are available. Feedback is welcome!

Type Lambdas

Let’s suppose we wanted to use a type class to add a new map method, call it map2, to various types. (For simplicity, I’ll just call the regular map method when it exists…). Here’s how we might define it and implement given instances for Seq[A] and Option[A]:

Recall that I described this new way of defining type classes and extension methods in a previous post. Note the two givens are anonymous. I could have written given SeqFunctor: Functor[Seq] with ... and similarly for Option.

Let’s confirm it works:

The comment is a reminder of how to import all the givens when they are defined somewhere else.

This code works as you might expect, but what if we wanted to extend Map[K,V]? The problem is we have two type parameters, instead of one. This is where type lambdas come in.

Here is a type alias MapKV defined as a type lambda for Map[K,V], followed by a given that uses it to let us apply map2 over the values of a map, leaving the keys unchanged:

The MapKV type alias looks like a curried function, with the symbol =>> between each type. Recall that an analogous curried function would have the type signature K => V => Map[K,V], as we’ll explore below.

The crucial point is that we can apply one type argument at a time. Compare the Functor[MapKV[K]] signature to the previous Functor[Seq] signature above. We apply K, returning a new type equivalent to [V] =>> Map[K,V]. The single type parameter V is what we need for the type class instance, just as we needed a single type parameter A for the given for sequences and options.

Notice what the REPL prints for the type of MapKV as MapKV[K] = [V] =>> Map[K, V]. There is a correspondence between the way we’ve traditionally wrote type aliases with type parameters, like MapKV[K] = …, and type lambdas MapKV = [K] => …. Incidentally, you could also define type MapKV2[K,V] = MapKV[K][V].

The type parameters can have lower and upper bounds, like [A <: AnyRef], but not context bounds, like [T: Numeric].

It was possible to simulate type lambdas in Scala 2 with a clever “hack”. Here’s an implementation for Either[L,R]:

There is nothing special about my use of the lambda and alpha characters; they were used a lot in Scala 2 examples. Here, we’re defining an anonymous type with a type alias λ that takes a single type parameter. That type alias is projected out of the anonymous class with #λ.

Polymorphic Functions

I compared the MapKV type alias to a function of type K => V => Map[K,V], but until Scala 3, we could only define functions with concrete types for K and V. However, Scala 2 did support polymorphic methods:

Scala 3 now lets us define polymorphic functions:

The list of type parameters is added before everything else, [K,V] => here. toMapF1g (“toMap function 1 — good”) lets the compiler infer the function type, while toMapF2g explicitly provides the type signature. Note that signature shown in the REPL for both of them. The compiler implements these functions with a new library type, PolyFunction, defining the apply method, similar to how non-parameterized functions are implemented.

Note: [K,V] => must start the body of toMapF2g, as well as appear at the start of the type signature. If you omit it from the body, the compiler says that K and V are undefined.

The toMapF*b functions demonstrate that “currying” the type parameters isn’t supported, but perhaps a future release of Scala 3 will add this.

Like type lambdas, the type parameters can have lower and upper bounds, like [A <: AnyRef], but not context bounds, like [T: Numeric].

To put type lambdas and polymorphic functions together, here’s an interesting example from this excellent scala-lang.org post on Tuples. You can map over the tuple elements, where the function passed to map has to be a PolyFunction:

So the tuple map function requires a PolyFunction. The actual type X will be inferred for the type of each tuple element.

Dependent Function Types

This subject doesn’t have much to do with the rest of this post, but it’s a second example of adding to functions a feature that has been available for methods, namely dependent return types.

Both the methods head and tail, as well as the functions h and t, have dependent return types, ll.Item, where the actual type will depend on the instantiated LinkedList.

Now let’s confirm that the methods and functions work. Notice the types shown:

Recap

Type lambdas make it much easier to define parameterized type aliases with “currying”, so we can apply one or more of the type parameters as needed. The syntax is deliberately designed to resemble “value lambdas”, which you may know as functions 🤓.

Functions gain two features that methods enjoyed. They can now have parameterized types and they can have dependent return types.

You can start reading the rough draft of Programming Scala, Third Edition on the O’Reilly Learning Platform. Currently, the first six chapters are available, including the two (five and six) that cover contextual abstractions.