Scala – What are type lambdas in Scala and what are their benefits

scalatypes

Sometime I stumble into the semi-mysterious notation of 

def f[T](..) = new T[({type l[A]=SomeType[A,..]})#l] {..}

in Scala blog posts, which give it a "we used that type-lambda trick" handwave.

While I have some intutition about this (we gain an anonymous type parameter A without having to pollute the definition with it?), I found no clear source describing what the type lambda trick is, and what are its benefits. Is it just syntactic sugar, or does it open some new dimensions?

Best Answer

Type lambdas are vital quite a bit of the time when you are working with higher-kinded types.

Consider a simple example of defining a monad for the right projection of Either[A, B]. The monad typeclass looks like this:

trait Monad[M[_]] {
  def point[A](a: A): M[A]
  def bind[A, B](m: M[A])(f: A => M[B]): M[B]
}

Now, Either is a type constructor of two arguments, but to implement Monad, you need to give it a type constructor of one argument. The solution to this is to use a type lambda:

class EitherMonad[A] extends Monad[({type λ[α] = Either[A, α]})#λ] {
  def point[B](b: B): Either[A, B]
  def bind[B, C](m: Either[A, B])(f: B => Either[A, C]): Either[A, C]
}

This is an example of currying in the type system - you have curried the type of Either, such that when you want to create an instance of EitherMonad, you have to specify one of the types; the other of course is supplied at the time you call point or bind.

The type lambda trick exploits the fact that an empty block in a type position creates an anonymous structural type. We then use the # syntax to get a type member.

In some cases, you may need more sophisticated type lambdas that are a pain to write out inline. Here's an example from my code from today:

// types X and E are defined in an enclosing scope
private[iteratee] class FG[F[_[_], _], G[_]] {
  type FGA[A] = F[G, A]
  type IterateeM[A] = IterateeT[X, E, FGA, A] 
}

This class exists exclusively so that I can use a name like FG[F, G]#IterateeM to refer to the type of the IterateeT monad specialized to some transformer version of a second monad which is specialized to some third monad. When you start to stack, these kinds of constructs become very necessary. I never instantiate an FG, of course; it's just there as a hack to let me express what I want in the type system.

Related Topic