泛函编程（34）－泛函变量：处理状态转变－ST Monad

  泛函编程的核心模式就是函数组合（compositionality）。实现函数组合的必要条件之一就是参与组合的各方程序都必须是纯代码的（pure code）。所谓纯代码就是程序中的所有表达式都必须是Referentially Transparent（RT，等量可替换的），它的意思是：在一段程序p中，所有的表达式e都可以用e的运算结果替代而不影响到p的运算结果，那么e就是RT等量可替换的，也就是说程序p是由纯代码组成的。但如果程序p中包含了一些变量，这些变量的状态就会影响到程序中e的运算结果，那么p就不再是纯代码了，也就无法保证函数组合的正确性了。所以在泛函编程模式中好像是禁止任何状态变化的（state mutation）。但实际上泛函编程并没有任何明文禁止一个函数内部使用状态转变，所以：如果一个函数f(x)的输入参数x是RT等量可替换的，那么函数f还是个纯函数（pure function）。

    为了方便或者提高运算效率，我们往往可能在一个函数内部使用一些变量（local variables）。如果这些变量的状态转变只体现在函数内部，那么对于这个函数的用户来说，这是个纯函数，使用这个函数进行函数组合是没有问题的。我们看看下面的这个例子：

 1   def quicksort(xs: List[Int]): List[Int] = if (xs.isEmpty) xs else {
 2     val arr = xs.toArray
 3     def swap(x: Int, y: Int) = {
 4       val tmp = arr(x)
 5       arr(x) = arr(y)
 6       arr(y) = tmp
 7     }
 8     def partition(l: Int, r: Int, pivot: Int) = {
 9       val pivotVal = arr(pivot)
10       swap(pivot, r)
11       var j = l
12       for (i <- l until r) if (arr(i) < pivotVal) {
13         swap(i, j)
14         j += 1
15       }
16       swap(j, r)
17       j
18     }
19     def qs(l: Int, r: Int): Unit = if (l < r) {
20       val pi = partition(l, r, l + (r - l) / 2)
21       qs(l, pi - 1)
22       qs(pi + 1, r)
23     }
24     qs(0, arr.length - 1)
25     arr.toList
26   }
27 }

以上函数即使使用了while loop, 变量var及可变数组Array，但这些都被限制在函数内部，所以quicksort还是个纯函数。

但是，使用了局部变量后往往迫使代码变得很臃肿。程序变得复杂影响了代码的理解、维护及重复利用。

泛函编程采用的是一种处理变量状态变化的编程语言。在前面我们已经讨论过State Monad，它可以对状态进行读写。State Monad的运作模式是：S => (A,S)，即：传入一个状态S，产生一个新的值及新的状态。对于处理本地状态转变，我们不是要对传入的S进行处理，而是把它作为一种标记让拥有同样标示S的函数可以对变量进行转变。

针对以上需求，一个新的数据类型产生了：ST Monad，我们看看它的定义：

 1 trait ST[S,A] { self =>
 2     protected def run(s: S): (A,S)
 3     def map[B](f: A => B): ST[S,B] = new ST[S,B] {
 4         def run(s: S) = {
 5             val (a1,s1) = self.run(s)
 6             (f(a1),s1)
 7         }
 8     }
 9     def flatMap[B](f: A => ST[S,B]): ST[S,B] = new ST[S,B] {
10         def run(s: S) = {
11             val (a1,s1) = self.run(s)
12             f(a1).run(s1)
13         }
14     }
15 }
16 object ST {
17     def apply[S,A](a: A): ST[S,A] = {
18         lazy val memo = a
19         new ST[S,A] {
20           def run(s: S) = (memo, s)
21         }
22     }
23 }

这个ST和State基本上一致，只是状态转变函数run不对外开放：protected def run(s: S): (A,S)，这是由于S代表了可以转变状态的权限，我们希望把这个权利局限在ST类内部。ST实现了flatMap，所以是个Monad。

我们希望达到的目的是通过内存参考（memory reference）对变量状态转变进行控制。我们需要实现的方法包括：

分配新的内存单元（memory cell）

读取内存单元数据

存写内存单元数据

ST是个Monad，我们可以制造一个for-comprehension的Monadic语言来进行泛函变量状态转变。我们的变量类型数据结构封装了一个变量：protected var，如下：

 1 trait STRef[S,A] {
 2     protected var cell: A
 3     def read: ST[S,A] = ST(cell)
 4     def write(a: A): ST[S,Unit] = new ST[S,Unit] {
 5         def run(s: S) = {
 6             cell = a
 7             ((),s)
 8         }
 9     } 
10 }
11 object STRef {
12     def apply[S,A](a: A): ST[S,STRef[S,A]] = ST(new STRef[S,A] {
13         var cell = a
14    })
15 }

 1 for {
 2     r1 <- STRef[Nothing,Int](1)
 3     r2 <- STRef[Nothing,Int](2)
 4     x <- r1.read
 5     y <- r2.read
 6     _ <- r1.write(y + 1)
 7     _ <- r2.write(x + 1)
 8     a <- r1.read
 9     b <- r2.read
10 } yield (a,b)

下一步就是如何运算以上的表达式了。我们希望能安全的运算变量状态转变，那么考虑以下两种ST操作：

ST[S,STRef[S,A]

ST[S,Int]

前面的ST动作包括了一个变量参考，使用者能通过STRef来修改变量，这个操作是不安全的。

ST[S,Int]包含了一个值，所以这个ST动作是安全的。

我们希望借scala的类系统（type system）来帮助我们阻止不安全的ST操作成功编译（compile）。具体实现方式如下：

1 trait RunnableST[A] {
2     def apply[S]: ST[S,A]
3 }

 1 object ST {
 2     def apply[S,A](a: A): ST[S,A] = {
 3         lazy val memo = a
 4         new ST[S,A] {
 5           def run(s: S) = (memo, s)
 6         }
 7     }
 8   def runST[S,A](rst: RunnableST[A]) = 
 9     rst[Null].run(null)._1
10 }

 1 val prg = new RunnableST[(Int,Int)] {
 2   def apply[S] = for {
 3       r1 <- STRef(1)
 4       r2 <- STRef(2)
 5       x <- r1.read
 6       y <- r2.read
 7       _ <- r1.write(y+1)
 8       _ <- r2.write(x+1)
 9       a <- r1.read
10       b <- r2.read
11   } yield (a,b)
12 }                                                 //> prg  : ch14.ex2.RunnableST[(Int, Int)] = ch14.ex2$$anonfun$main$1$$anon$6@6
13                                                   //| 108b2d7
14 ST.runST(prg)                                     //> res1: (Int, Int) = (3,2)

 1 class STArray[S,A] (implicit manifest: Manifest[A]) {
 2   protected val value: Array[A]
 3   //array 长度
 4   def size: ST[S,Int] = ST(value.size)
 5   //读取array i 位置
 6   def read(i: Int): ST[S,A] = ST(value(i))
 7   //将a写入array i 位置
 8   def write(i: Int, a: A): ST[S,Unit] = new ST[S,Unit] {
 9       def run(s: S) = {
10           value(i) = a
11           ((),s)
12       }
13   }
14   //将可变array转换成不可变list
15   def freeze: ST[S,List[A]] = ST(value.toList)
16   //按照Map的指引，把Map.v写入array Map.k位置
17   def fill(xs: Map[Int,A]): ST[S,Unit] =
18     xs.foldRight(ST[S,Unit](())) {
19       case ((k,v), st) => st flatMap {_ => write(k,v)}
20     }
21    //array位置i,j内容互换
22    def swap(i: Int, j: Int): ST[S,Unit] = for {
23     x <- read(i)
24     y <- read(j)
25     _ <- write(i, y)
26     _ <- write(j, x)
27   } yield ()
28 
29 }
30 object STArray {
31 //建一个长度为sz,初始值为v的array
32     def apply[S,A: Manifest](sz: Int, v: A) = ST(new STArray[S,A] {
33         lazy val value = Array.fill(sz)(v)
34     })
35     //把一个List转成STArray
36     def fromList[S,A: Manifest](xs: List[A]): ST[S, STArray[S,A]] = ST(new STArray[S,A] {
37         lazy val value = xs.toArray
38     })
39 }

 1 object Immutable {
 2   def noop[S] = ST[S,Unit](())
 3 
 4   def partition[S](a: STArray[S,Int], l: Int, r: Int, pivot: Int): ST[S,Int] = for {
 5     vp <- a.read(pivot)
 6     _ <- a.swap(pivot, r)
 7     j <- STRef(l)
 8     _ <- (l until r).foldLeft(noop[S])((s, i) => for {
 9       _ <- s
10       vi <- a.read(i)
11       _  <- if (vi < vp) (for {
12         vj <- j.read
13         _  <- a.swap(i, vj)
14         _  <- j.write(vj + 1)
15       } yield ()) else noop[S]
16     } yield ())
17     x <- j.read
18     _ <- a.swap(x, r)
19   } yield x
20 
21   def qs[S](a: STArray[S,Int], l: Int, r: Int): ST[S, Unit] = if (l < r) for {
22     pi <- partition(a, l, r, l + (r - l) / 2)
23     _ <- qs(a, l, pi - 1)
24     _ <- qs(a, pi + 1, r)
25   } yield () else noop[S]
26 
27   def quicksort(xs: List[Int]): List[Int] =
28     if (xs.isEmpty) xs else ST.runST(new RunnableST[List[Int]] {
29       def apply[S] = for {
30         arr    <- STArray.fromList(xs)
31         size   <- arr.size
32         _      <- qs(arr, 0, size - 1)
33         sorted <- arr.freeze
34       } yield sorted
35   })
36 }