Scala developers might have heard of “type lambdas”, a fairly horrendous-looking construction that sometimes appears in code using higher-kinded types. What is a type lambda, why would we ever want to use one, and even better, how can we avoid having to write them? In this blog post we tackle these questions.

The need for type lambdas usually arises
when dealing with higher-kinded types.
These are type constructors that take other types
(or even other type constructor) as parameter.
A familiar example is `List`

.
`List`

by itself is not a type.
You need to provide a parameter as `Int`

to create a type such as `List[Int]`

.
We call `List`

a type constructor.
When we declare a type variable that is a type constructor,
we write `F[_]`

to indicate that `F`

needs
to be provided with a type to construct a concrete type.

## Type aliases

Scala developers will be familiar with declaring *type aliases*:

```
type L = List[(Option[(Int,Double)])]
```

We can use `L`

in any place
where we can use the unwieldy expression on the right side.

We can also also declare type aliases that take parameters:

```
type T[A] = Option[Map[Int, A]]
val t: T[String] = Some(Map(1 -> "abc", 2 -> "xyz"))
```

Often type aliases are simply used as a convenience, but sometimes their use is required as in the following example.

Let’s define a type parameterised on another type constructor
(we’ll call it `Functor`

to link to a real-world example,
but could be anything else of the same kind—don’t let the name confuse you).
We’ll see what parameters we are allowed to use with it.
Remember that it is expecting a type constructor with *one* parameter:

```
trait Functor[F[_]]
type F1 = Functor[Option] // OK
type F2 = Functor[List] // OK
type F3 = Functor[Map] // !!
// error: Map takes two type parameters, expected: one
// type fo = Functor[Map]
// ^
```

The compiler error message indicates the problem:
Map takes two type parameters (`Map[K,V]`

)
while the type parameter to `Functor`

expects one.
Type aliases are often used to
‘partially apply’ a type constructor
and so to ‘adapt’ the *kind* of the type to be used:

```
type IntKeyMap[A] = Map[Int, A]
type F3 = Functor[IntKeyMap] // OK
```

`IntKeyMap`

now takes a single type parameter,
and the compiler is happy with that.
This works fine,
but can we achieve the same goal
without having to declare an alias?
We could try to mirror the syntax of partially-applied
*value*-level functions, with the underscore syntax, as in:

```
val cube = Math.pow(_: Double, 3) // cube: Double => Double
cube(2) // 8
```

But this syntax doesn’t do the same thing with types:

```
type F4 = Functor[Map[Int, _]]
// error: Map[Int, _] takes no type parameters, expected: one
// type F4 = Functor[Map[Int, _]]
// ^
```

Scala uses the underscore in different
(one could say inconsistent)
ways depending on the context.
In this case (in the right hand side of the type alias definition)
what is implied is not partial application at all,
but rather “I don’t care what this type is”.
This is known as an *existential type* if you want to read up further.

There is, in fact, currently no direct syntax for partial application of type constructors in Scala.

## Type lambdas

We can solve this problem of partially applying types
by using a *type lambda*.
Let’s return to our example:

```
({ type T[A] = Map[Int, A] })#T
```

The heart of the expression above appears to be exactly the same as declaring a type alias, but can be used inline:

```
type F5 = Functor[({ type T[A] = Map[Int, A] })#T] // OK
```

We can read the type lambda syntax as:
declaring an anonymous type,
inside of which we define the desired type alias,
and then accessing its type member with the `#`

syntax.

It’s easy to argue that the construction above is more offensive to the eye than using an extra line to declare a type alias the traditional way. Indeed we recommend using a type alias whenever possible to keep your code clean and readable. However, sometimes type lambdas are unavoidable. Consider the following rather abstract example:

```
def foo[A[_, _], B](functor: Functor[A[B, ?]]) // won't compile
```

This is not valid Scala,
but it is the quickest way to convey the intention.
Imagine that the `?`

behaves like the
partial type constructor application we mentioned earlier,
leaving the `functor`

argument as
a single unspecified type parameter.

Can we resolve the situation using a separate type alias?

```
type AB[C] = ... // what should we put here?
def foo[A[_,_], B](functor: Functor[AB])
```

The answer is no, because at the time at which we define `AB`

,
we don’t have `A`

and `B`

available.
Attempts to ‘pass them in’ as parameters like this:

```
type T[A, B, C] = ...
```

defeat the purpose because they alter the type arity.
We needed an arity of 1 to pass into `foo`

but now we’ve just increased it to 3,
which is clearly not going to go down with the compiler.

## Alternative encodings

What are the possible ways of implementing our `Functor`

example?

### Use a type lambda

We can use the type lambda after all:

```
def foo[A[_,_],B](functor: Functor[({type AB[C] = A[B,C]})#AB])
```

This works because the types `A`

and `B`

are available in the scope when we define `AB`

.

### Declare a surrounding class

If we prefer not to use type lambdas
we can split the definition of `foo`

in two:

```
class Foo[A[_,_],B] {
type AB[C] = A[B, C]
def apply(functor: Functor[AB]) = ...
}
def foo[A[_,_],B] = new Foo[A,B]
```

Like type lambdas, this technique allows us to
define `AB`

once `A`

and `B`

are already known.
However, this approach is verbose
and causes allocations at run time,
whereas the type lambda exists only within the compiler.

### Curried type constructors

A third *hypothetical* solution,
that is not currently possible
but would fix this issue cleanly,
is to use curried type constructors.
These are similar to
the partially applied type constructors
we hypothesised earlier.

Just as we can have multiple argument lists for methods:

```
def fill(n: Int)(elem: Double) = ...
val fill10 = fill(10) _ // fill10: Double => List[Double]
fill10(5.1)
// List(5.1, 5.1, 5.1, 5.1, 5.1, 5.1, 5.1, 5.1, 5.1, 5.1)
```

so we could, in principle, have the same at the type level:

```
type AB[A, B][C] = A[B, C]
```

We could then ‘partially apply’ this
(with the first argument list only: `AB[A, B]`

),
leaving behind the arity-1 type constructor we require:

```
type AB[A, B][C] = A[B, C] // (not valid syntax yet!)
def foo[A[_, _], B](functor: Functor[AB[A,B]])
```

While this approach is currently fantasy, there have been rumours about the introduction of curried or partially applied types in Dotty.

### Kind projector

While we wait for curried type constructors to become part of the language, we can find another solution in the kind projector compiler plugin.

Kind projector provides a clearer syntax for type lambdas. For example, we can implement our functor from above as follows:

```
type F = Functor[Map[Int, ?]] // now works!
def foo[A[_, _], B](functor: Functor[A[B, ?]]) // now works!
```

With this we get as close as we can
to our initial aim of writing types
as if we were partially applying type constructors.
The only difference is that we use `?`

to do it instead of `_`

,
which already has too many uses in Scala.

During compilation, kind projector translates
type expressions containing `?`

into regular type lambdas,
giving us the same semantics
with a large gain in readability.
Kind projector doesn’t work in *all* cases,
but for the most part it makes our lives a lot simpler!

## Conclusions

Type lambdas are an ugly but necessary concept in Scala for the time being. We can usually use a type alias to avoid having to write a type lambda. In many cases that we cannot use an alias, the kind projector compiler plugin will usually solve the problem.

For more discussion of type lambdas, see this blog post by Adil Akhter.

For more information about kind projector, see the project page on Github.