这个又是apocalisp上的一个短系列。正好最近看到有人讨论IO monad,我在看FP in scala中也到这部分了。顺便看一下,老规矩还是带私活的翻译。

State Monad

首先回到State Monad。 这里有个简单的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
case class World[S]()

case class ST[S, A](f: World[S] => (World[S], A)) {
def apply(s: World[S]): (World[S], A) = f(s)

def flatMap[B](g: A => ST[S, B]): ST[S, B] =
ST(s => {
val nst = f(s)
g(nst._2).f(nst._1)
})

def map[B](f: A => B): ST[S, B] =
flatMap(x => returnST(f(x)))
}

object ST {
def returnST[S, A](a: => A): ST[S, A] = ST(s => (s, a))
}

显然,这里的returnSTflatMap就是return>>=World类型代表要维护的状态。

到现在为止这还没什么特别的东西。接下来就是有意思的地方了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
case class STRef[S, A](a: A) { self =>
import ST._
private var value: A = a

def get: ST[S, A] = returnST(value)
def set(a: A): ST[S, STRef[S, A]] =
ST((s: World[S]) => {
value = a
(s, this)
})

def modify(f: A => A): ST[S, STRef[S, A]] = for {
a <- get
v <- set(f(a))
} yield v
}

其实回忆之前的State Monad的时候就已经实现过了getset等函数。

1
2
def get[S]: State[S, S] = State(s => (s, s))
def set[S](s: S) = State(_=> ((), s))

对比两者,我们很明显的发现,我们使用了STRef这个类型包装了一个Mutable Reference。而不是直接通过修改StateS

如果我们在ST本身包含一个run函数,我们就可以直接执行所有的state transformer了。但是这样我们就可以通过newVar(10).run,来获取一个裸的STRef这显然不是我们希望得到的。所以我们要自己实现一个。

Haskell中,runST的类型是

1
runST :: forall a. (forall s. ST s a) -> a.

这种rank-2 type,scala并不能直接写出来。(这确实是很麻烦的地方,尤其是ide的感知有时候还是错的)。不过这个类型体现了另外一个问题,我们把STRef的类型带进去。

1
forall a. (forall s. ST s (STRef s a)) -> STRef ??? a

问号那个地方应该怎么填呢?那个位置应该是可以满足任意的箭头的左面的s的。所以,没有办法暴露出一个裸的引用。

writing runST in Scala

为了实现runST这个函数,我们先实现那个Forall

1
2
3
trait Forall[P[_]] {
def apply[A]: P[A]
}

这样,我们就可以通过

1
2
def runST[A](forall: Forall[({type lambda[S] = ST[S, A]})#lambda]): A =
forall.apply.f(empty)._2

这里forall.apply这样就能拿到forall sST[S, A],然后为了方便我们再定义

1
type ForallST[A] = Forall[({type lambda[S] = ST[S, A]})#lambda]

这个具体的类型。

下面看个使用的例子

1
2
3
4
5
6
7
8
9
10
11
def e1[S]: ST[S, STRef[S, Int]] = for {
r <- ST.newVar[S, Int](12)
_ <- r.modify(_ + 1)
x <- r.modify(_ + 1)
_ <- r.modify(_ + 1)
} yield x


def e2[A] = e1[A].flatMap(_.get)

ST.runST(new ST.ForallST[Int]{def apply[A] = e2[A]})

这里可以试一试,怎么也写出来那种直接暴露出STRef的代码。

比如

1
runST(new Forall[({type λ[S] = ST[S, STRef[S, Int]]})#λ] { def apply[A] = e1 })

这种就无法通过编译。

在scala这种本来就包含var的类型的语言中,可能感觉这种行为没什么用,不过这么想,由于STRef不能暴露在ST monad之外,所以,我们可以控制变量的可变性的生存区。在需要变量的地方,使用变量,脱离这个区域就无法改变了。

其实ST给以我们以下三点

  • Mutations of an object are guaranteed to run in sequence(考虑在像haskell这种语言里面,都是lazy,对于没有依赖关系的变量并不保证求值顺序)。
  • The holder of a mutable object is guaranteed to hold the only reference to it(不会暴露出元对象)。
  • Once a sequence of mutations of an object terminates, that object is never mutated again(可变的生存期)。

Rúnar的描述是“This is much more than delay side-effects until the last possible moment”。我们依靠类型系统完成了内存可变性的控制。

这一部分的代码在这里

IO Monad

接下来就到IO monad了。

因为是IO Monad,我们看一下包含IO的情况。

还记得之前在Free Monad之中,我们做的,其实就是根据类型定义语法,然后实现解析器。这里,我们也将这么做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
sealed trait IO[A] {
sealed trait IO[A] {
def flatMap[B](f: A => IO[B]): IO[B] = FlapMap(this,f)
def map[B](f: A => B): IO[B] = flatMap(f andThen (Return(_)))
}

case class Return[A](a: A) extends IO[A]
case class Suspend[A](resume: () => A) extends IO[A]
case class FlapMap[A, B](sub: IO[A], k: A => IO[B]) extends IO[B]

object IO extends Monad[IO] {
def unit[A](a: A) = Return(a)
def flatMap[A, B](a: IO[A])(f: A => IO[B]) = a flatMap f
def suspend[A](a: => IO[A]) = Suspend(() => ()).flatMap(_ => a)
}

这里的三个类型,Return表示我们希望结束返回结果,Suspend表示我们希望一个凭空造出来的操作,FlatMap表示希望把多个操作连接起来。

然后,我们接着实现具体的解释器。

1
2
3
4
5
6
7
8
9
10
@annotation.tailrec
def run[A](io: IO[A]): A = io match {
case Return(a) => a
case Suspend(r) => r()
case FlatMap(x, f) => x match {
case Return(a) => run(f(a))
case Suspend(r) => run(f(r()))
case FlatMap(y, g) => run(y flatMap (a => g(a) flatMap f))
}
}

这里使用尾递归其实和循环是等价的,这种方法避免了都是递归stackoverflow的问题,这种方式叫做trampolining。而且,我们也发现,这里其实依旧是一个free monad。形式和之前的区别不大,就换了个名字。

我们先弄个简单的例子,计算阶乘。

首先是一些脚手架,

1
2
3
4
5
6
7
8
9
def PrintLine(s: String): IO[Unit] =
Suspend(() => Return(println(s)))

def ReadLine: IO[String] =
IO.suspend(Return(readLine()))

def readInt = ReadLine map (_.toInt)

def readInts = readInt ** readInt

把基本的操作,通过ReturnSuspend包装起来。然后是计算factorial的函数。

1
2
3
4
5
def factorial(n: Int): IO[Int] = for {
acc <- ref(1)
_ <- foreachM(1 to n toStream)(i => acc.modify(_ * i).skip)
result <- acc.get
} yield result

最后是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def factorialREPL: IO[Unit] = sequence_(
PrintLine(helpstring)
,
doWhile {
ReadLine
} { line =>
val ok = line != "q"
when(ok) {
for {
n <- factorial(line.toInt)
_ <- PrintLine("factorial: " + n)
} yield ()
}
}
)

最后在

1
run(factorialREPL)

就行了。

其实这里我们可以进一步,看看IO做了什么,首先,其实他和State区别不大,不过是World真的变成了World。其实想一想,在haskell里面,因为都是lazy的,所以如果两个变量没有依赖的话,并不保证求值顺序,那么我们常见的

1
2
val a = getLine()
val b = getLine()

不就不能保证顺序了?,这显然是不合理的,我们这样写其实默认了a要比b先一步执行,不论,我们在getLine得到b的时候是不是关心a的值。

再换个角度,这个时候的IO,如果我们放弃IO这个名字,run函数,改用循环。那我们实际就实现了一个taillrec展开的工具。用我们提供的语法实现的递归可以通过run来展开。

或者,我们修改Suspend的类型,让他真的Suspend起来。

1
case class Suspend[A](resume: Par[A])

这样在每次实际执行一个可能有副作用的函数的时候(从很慢的介质上读取数据,网络等),就会异步的在另一个线程执行。

这篇好乱,其实涉及IO monadeffect system还有free monad。我只是被类型系统的表达能力惊了。




X