这里来总结一下Scala类型系统中的Type Lambda，这是一个神奇的Trick，可以在类型上做有限的类似于Lambda Calculus的运算。

Type Lambda

为了便于理解，这里就以熟悉的Monad开始。首先定义我们的Monad Typeclass:

1
2
3
4
5
6
7

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

可以看出Monad的kind为(* -> *) -> *。

假如我们想为Either[+A, +B]类型的右投影(Right Projection)实现对应的Monad，这里就会出现一个问题：Either[+A, +B]类型的kind为* -> * -> *，而Monad最多接受kind为* -> *的type constructor，因此如果我们想把Either塞进Monad里，就必须将其kind化为* -> *。是不是很像在类型系统上进行Currying(柯里化)呢？这就是type lambda的作用。我们可以这样写：

1
2
3
4
5
6

trait EitherMonad[A] extends Monad[({type λ[α] = Either[A, α]})#λ] {
  override def unit[B](a: B): Either[A, B]
  override def >>=[B, C](m: Either[A, B])(f: B => Either[A, C]): Either[A, C]
}

下面我们来分析一下此Monad对应的type parameter是什么玩意儿。首先，{type λ[α] = Either[A, α]}这一块是一个structural type，在其内部定义了一个类型λ，接受一个类型参数α，此类型与Either[A, α]类型相对应。也就是说这个类型相当于Either[A, _]这个type constructor，它再接受一个类型参数从而构造出完整的Either[A, B]类型(kind为*)。接着我们通过类型投影（#操作符）得到这个λ类型（通过反射），它的kind为* -> *，从而符合Monad类型参数的要求。

这样的trick就是Type Lambda，它相当于在类型系统上(对type constructor)进行Currying。我们可以看到它的实现非常巧妙，巧妙地利用了structural type和type projection。

我们类比一下Currying。比如有函数（为了表示方便，这里用Haskell函数表示）：

1

f :: (Int a) => a -> b -> c

我们可以对其进行Currying：

1
2
3
4

f :: (Int a) => a -> (b -> c)
g :: b -> c
g = f 0 {- eta reduction -}

同样，在类型系统上我们也可以这么干，比如我们要将kind为* -> * -> *的Either[A, B]化为kind为* -> *的Either[A, _]，这时候我们就可以利用type lambda来进行转化。

题外话（关于Haskell）：这样的操作其实属于类型组合(type composition)。Haskell中的Control.Compose模块提供了一系列的用于类型组合的玩意，有兴趣的可以看看Hackage中的文档玩一玩～

References

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