Monad in Scala

Scala有很强的类型系统。加上一些隐式规则，我们可以在scala里模拟haskell的monad。

先从haskell的monad type class开始：

class Monad M where
ret :: a -> M a
bind :: M a -> (b -> M b) -> M b

这里M是type class的参数。它是一个高阶类型， kind是 * –> *。认识到这个很重要，因为如果我们想在scala里面模拟，我们首先需要知道是否scala提供了相应的东西。

幸运的是，scala支持高级类型： M[_]， 所以对应的我们可以用scala的traits表示如下：

trait Monad[M[_]] {
def ret[A](a: A) : M[A]
def bind[A, B](fa: M[A], f: A => M[B]) : M[B]
}

有了class，我们再看如何定义instance。

这里我们给出State实例，因为可以演示scala高级类型柯瑞化。

先给出state type：

data State s a = State { runState:: s -> (s, a)}

代数类型State有两个参数，所以它的kind是* –> * –> *。你可能发现它和Monad参数的kind不一样，那我们如何能给出State的Monad instance呢？

简单，先传一个参数(State s)，这样它的kind就是* –> *了（柯瑞化），于是我们有了下面的instance。

instance Monad (State s) where
ret a = State (\s –> (s, a))
bind (State fa) f = State $ \s ->
let (s0, a0) = fa s
(State fb) = f a0
in fb s0

对应的在scala里我们先定义代数类型State。可以用一般的class，但是最简单的是用case class。

case class State[S, A](runState : S => (S, A))

为了模拟对不同的type，对应不同的Monad实现，我们需要在scala里的type system里给出一个映射关系。

我们可以需要利用隐式参数：

object Monad {
def apply[M[_]](implicit m : Monad[M]) : Monad[M] = m
}

这里有一个技巧，由于apply没有参数，Monad[T] === Monad.apply[T]，于是我们可以通过Monad[T]来得到不同Monad实例。T的不同得到的实例也不同。

现在实现一个State的隐身规则，就可以相当于插入了一个从State到实例的映射关系。

object StateMonad {
implicit def stateToMonad[S] = new Monad[({type M[a] = State[S, a]})#M] {
def ret[A](a: A) = new State[S, A](s => (s, a))
def bind[A, B](a: State[S, A], f: A => State[S, B]) = new State((s: S) => {
val State(f0) = a
val (s0, a0) = f0(s)
val State(f1) = f(a0)
f1(s0)
})
}
}

你可能发现了一个奇怪的东西 ({type M[a] = State[S, a]})#M。其实就是一个多参数类型的柯瑞化。

你可能像为什么Scala不支持这样写 State[S, _]？我也不知道。。。

scala只支持一个参数的量化，但是可以通过其他方法来完成柯瑞化。

上面的奇怪东西其实等价于下面的代码：

trait SM[S] {
type M[a] = State[S, a]
}

({type M[a] = State[S, a]})#M == SM[S]#M

‘#’被用来访问内部类型别名。{…}其实就是一个匿名的类型，不过通常我们用来它来做structural typing。

好了，现在我们可以使用了：

import StateMonad._
def main {
val s = Monad[SM[Int]#M].ret(0)
Monad[SM[Int]#M].bind(s, (a:Int) => s)
}