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

Question

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.

The benefits are exactly the same as those conferred by anonymous functions.

def inc(a: Int) = a + 1; List(1, 2, 3).map(inc)

List(1, 2, 3).map(a => a + 1)

An example usage, with Scalaz 7. We want to use a Functor that can map a function over the second element in a Tuple2.

type IntTuple[+A]=(Int, A)
Functor[IntTuple].map((1, 2))(a => a + 1)) // (1, 3)

Functor[({type l[a] = (Int, a)})#l].map((1, 2))(a => a + 1)) // (1, 3)

Scalaz provides some implicit conversions that can infer the type argument to Functor, so we often avoid writing these altogether. The previous line can be rewritten as:

(1, 2).map(a => a + 1) // (1, 3)

If you use IntelliJ, you can enable Settings, Code Style, Scala, Folding, Type Lambdas. This then hides the crufty parts of the syntax, and presents the more palatable:

Functor[[a]=(Int, a)].map((1, 2))(a => a + 1)) // (1, 3)

A future version of Scala might directly support such a syntax.

To put things in context: This answer was originally posted in another thread. You are seeing it here because the two threads have been merged. The question statement in the said thread was as follows:

How to resolve this type definition: Pure[({type ?[a]=(R, a)})#?] ?

What are the reasons of using such construction?

Snipped comes from scalaz library:

trait Pure[P[_]] {
  def pure[A](a: => A): P[A]
}

object Pure {
  import Scalaz._
//...
  implicit def Tuple2Pure[R: Zero]: Pure[({type ?[a]=(R, a)})#?] = new Pure[({type ?[a]=(R, a)})#?] {
  def pure[A](a: => A) = (Ø, a)
  }

//...
}

---

Answer:

trait Pure[P[_]] {
  def pure[A](a: => A): P[A]
}

The one underscore in the boxes after P implies that it is a type constructor takes one type and returns another type. Examples of type constructors with this kind: List, Option.

Give List an Int, a concrete type, and it gives you List[Int], another concrete type. Give List a String and it gives you List[String]. Etc.

So, List, Option can be considered to be type level functions of arity 1. Formally we say, they have a kind * -> *. The asterisk denotes a type.

Now Tuple2[_, _] is a type constructor with kind (*, *) -> * i.e. you need to give it two types to get a new type.

Since their signatures do not match, you cannot substitute Tuple2 for P. What you need to do is partially apply Tuple2 on one of its arguments, which will give us a type constructor with kind * -> *, and we can substitue it for P.

Unfortunately Scala has no special syntax for partial application of type constructors, and so we have to resort to the monstrosity called type lambdas. (What you have in your example.) They are called that because they are analogous to lambda expressions that exist at value level.

The following example might help:

// VALUE LEVEL

// foo has signature: (String, String) => String
scala> def foo(x: String, y: String): String = x + " " + y
foo: (x: String, y: String)String

// world wants a parameter of type String => String    
scala> def world(f: String => String): String = f("world")
world: (f: String => String)String

// So we use a lambda expression that partially applies foo on one parameter
// to yield a value of type String => String
scala> world(x => foo("hello", x))
res0: String = hello world


// TYPE LEVEL

// Foo has a kind (*, *) -> *
scala> type Foo[A, B] = Map[A, B]
defined type alias Foo

// World wants a parameter of kind * -> *
scala> type World[M[_]] = M[Int]
defined type alias World

// So we use a lambda lambda that partially applies Foo on one parameter
// to yield a type of kind * -> *
scala> type X[A] = World[({ type M[A] = Foo[String, A] })#M]
defined type alias X

// Test the equality of two types. (If this compiles, it means they're equal.)
scala> implicitly[X[Int] =:= Foo[String, Int]]
res2: =:=[X[Int],Foo[String,Int]] = <function1>

Edit:

More value level and type level parallels.

// VALUE LEVEL

// Instead of a lambda, you can define a named function beforehand...
scala> val g: String => String = x => foo("hello", x)
g: String => String = <function1>

// ...and use it.
scala> world(g)
res3: String = hello world

// TYPE LEVEL

// Same applies at type level too.
scala> type G[A] = Foo[String, A]
defined type alias G

scala> implicitly[X =:= Foo[String, Int]]
res5: =:=[X,Foo[String,Int]] = <function1>

scala> type T = World[G]
defined type alias T

scala> implicitly[T =:= Foo[String, Int]]
res6: =:=[T,Foo[String,Int]] = <function1>

In the case you have presented, the type parameter R is local to function Tuple2Pure and so you cannot simply define type PartialTuple2[A] = Tuple2[R, A], because there is simply no place where you can put that synonym.

To deal with such a case, I use the following trick that makes use of type members. (Hopefully the example is self-explanatory.)

scala> type Partial2[F[_, _], A] = {
     |   type Get[B] = F[A, B]
     | }
defined type alias Partial2

scala> implicit def Tuple2Pure[R]: Pure[Partial2[Tuple2, R]#Get] = sys.error("")
Tuple2Pure: [R]=> Pure[[B](R, B)]