泛函编程(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 }

可以看到,STRef的读写访问都返回ST。这使得我们可以用ST Monad语言来描述变量状态转变,如下:

 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 }

我们先增加一个新的类型RunnableST。把类参数S嵌入在RunnableST类内部的apply方法里。这样可以有效防止new RunnableST[STRef[Nothing,Int]]这样的语句通过编译。再增加一个可以运算ST的函数runST:

 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)

我们知道,Array类型也是一种内存参考。我们也可以建一个基于Array的泛函变量数据类型:

 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 }

再看看用STArray的例子:

 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 }

从以上的讨论我们了解到:泛函变量状态变化是先用Monadic语言描述状态转变然后通过类系统来实现安全运算的。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xx_Cc的学习总结专栏

iOS底层原理总结 - 探寻Runtime本质(二)

1542
来自专栏CodeSheep的技术分享

Java编程思想学习录(连载之:内部类)

19811
来自专栏待你如初见

Day14

953
来自专栏Linux驱动

快速排序(详解)

描述: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序...

1839
来自专栏书山有路勤为径

复杂的链表的深度拷贝

Copy List with Random Pointer 已知一个复杂的链表,节点中有一个指向本链表任意某个节点的碎甲指针(也可以为空),求这个链表的深度拷...

591
来自专栏zaking's

用js来实现那些数据结构06(队列)

  其实队列跟栈有很多相似的地方,包括其中的一些方法和使用方式,只是队列使用了与栈完全不同的原则,栈是后进先出原则,而队列是先进先出(First In Firs...

2926
来自专栏你不就像风一样

Java核心数据结构(List,Map,Set)使用技巧与优化

JDK提供了一组主要的数据结构实现,如List、Map、Set等常用数据结构。这些数据都继承自 java.util.Collection 接口,并位于 java...

1313
来自专栏Java技术

Java性能优化之字符串优化处理

String对象是java中重要的数据类型,在大部分情况下我们都会用到String对象。其实在Java语言中,其设计者也对String做了大量的优化工作,这些也...

885
来自专栏Spring相关

thymeleaf的th:each常见用法

4493
来自专栏程序生活

Tensorflow教程(十三) tf.Variable() 和tf.get_variable()1 简介2 区别3 实例

1543

扫码关注云+社区