Scala | Type Lambda

这里来总结一下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

文章目录
  1. 1. Type Lambda
  2. 2. References