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

Question

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?

Answer 1

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.