泛函编程(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 条评论
登录 后参与评论

相关文章

来自专栏Java技术栈

Java内存泄漏介绍

内存管理是Java最重要的优势之一,你只需创建对象,Java垃圾收集器会自动负责分配和释放内存。但是,情况并不那么简单,因为在Java应用程序中经常发生内存泄漏...

3357
来自专栏Golang语言社区

Golang指针与nil浅析

曾经听说过一句话,编程的本质就是指针和递归。那会刚开始编码,只是这两个的概念有个感性粗浅的认识。最早接触指针,莫过于C语言了,能否理解用好指针也成为一个合格C语...

2676
来自专栏pangguoming

理解闭包 js回收机制

为什么要有回收机制?why? 打个比方,我有一个内存卡,这个内存是8G的,我把文件,视频,音乐,都保存到了这个内存卡,随着我的储存的内容越来越多,这个内存卡已经...

3547
来自专栏Java后端技术

Java Collection、Map集合总结

      依赖hashCode()和equals()两个方法进行保证元素唯一性,开发中使用开发工具自动生成就好。

472
来自专栏iOS技术杂谈

Java8 Lambda表达式与Stream API (二): Stream API的使用你要知道的Java8 匿名内部类、函数式接口、lambda表达式与Stream API都在这里

你要知道的Java8 匿名内部类、函数式接口、lambda表达式与Stream API都在这里 转载请注明出处 https://cloud.tencent.co...

3696
来自专栏阮一峰的网络日志

Ramda 函数库参考教程

学习函数式编程的过程中,我接触到了 Ramda.js。 我发现,这是一个很重要的库,提供了许多有用的方法,每个 JavaScript 程序员都应该掌握这个工具。...

3746
来自专栏章鱼的慢慢技术路

C++笔试面试题整理

封装来源于信息隐藏的设计理念,是通过特性和行为的组合来创建新数据类型让接口与具体实现相隔离。

1513
来自专栏柠檬先生

Less 常用基础知识

LESS 中的注释   也可以额使用css 中的注释(/**/) 这种方式是可以被编译出来的。   也可以使用// 注释 不会被编译的 变量 ...

1916
来自专栏博岩Java大讲堂

我眼中的Java-Type体系(1)1.ParameterizedType2.TypeVariable3.GenericArrayType4.Class5.WildcardType

3026
来自专栏菩提树下的杨过

ruby学习笔记(7)-闭包

闭包的一个重要特征是:过程(方法)内部定义的变量,即使在方法调用完成以后,仍然可以继续引用到!(即延长了生命周期) def method(n) puts "n...

1695

扫码关注云+社区