Scala有很强的类型系统。加上一些隐式规则,我们可以在scala里模拟haskell的monad。
先从haskell的monad type class开始:
class Monad M whereret :: a
-> M abind :: 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) whereret 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) = aval (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)}