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?

Solution 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.

Solution 2

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.

Solution 3

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)]

Comments

[Shelby Moore III]

See also.

[AndreasScheinert]

That last snippet looks really nice. IntelliJ scala plugin surely is awesome!

[Dan Burton]

Interesting to note that Haskell does not directly support type-level lambdas, although some newtype hackery (e.g. the TypeCompose library) has ways to sort of get around that.

[ron]

Thanks! The lambda may be missing in the last example. Aside, why do tuple functors chose to transform the last value? Is it convention / a practical default?

[Daniel Spiewak]

I'd be curious to see you define the bind method for your EitherMonad class. :-) Aside from that, if I may channel Adriaan for a second here, you're not using higher-kinded types in that example. You are in FG, but not in EitherMonad. Rather, you are using type constructors, which have kind * => *. This kind is of order-1, which is not "higher".

[Kris Nuttycombe]

I thought that kind * was order-1, but in any case Monad has kind (* => *) => *. Also, you'll note that I specified "the right projection of Either[A, B]" - the implementation is trivial (but a good exercise if you haven't done it before!)

[Randall Schulz]

I'm running nightlies for Nika and I don't have the IDEA option described. Interestingly enough, there is an inspection for "Applied Type Lambda can be simplified."

[retronym]

It's moved to Settings -> Editor -> Code Folding.

[Kevin Meredith]

@retronym, I got an error when trying (1, 2).map(a => a + 1) in REPL: ` <console>:11: error: value map is not a member of (Int, Int) (1, 2).map(a => a + 1) ^`

[jhegedus]

I gues Daniel's point not calling *=>* higher is justified by the analogy that we do not call an ordinary function (that maps non functions to non functions, in other words, plain values to plain values) higher order function.

[jhegedus]

Pierce's TAPL book, page 442: Type expressions with kinds like (*⇒*)⇒* are called higher-order typeoperators.

[Max Heiber]

The "hides the crufy parts of the syntax" link is broken.

[qtwo]

Scala 3 has brought in a simpler syntax for type lambdas. With the new syntax, EitherMonad definition above becomes EitherMonad[A] extends Monad[[α] =>> Either[A, α]]