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)

}


分享给朋友:
您可能感兴趣的文章:
随机阅读: