泛函编程(15)-泛函状态-随意数产生器

   对于OOP程序员来说,泛函状态变迁(functional state transition)是一个陌生的课题。泛函状态变迁是通过泛函状态数据类型(functional state)来实现的。State是一个出现在泛函编程里的类型(type)。与其它数据类型一样,State同样需要自身的一套泛函操作函数和组合函数(combinators),我们将在以下章节中讨论有关State数据类型的设计方案。

     在正式介绍State类型前,我们先从随意数产生器(RNG: Random Number Generator)开始,从泛函RNG的原理分析引领到State设计方案。

先看看我们熟悉的java RNG:

1 //java code
2 val rng = new java.util.Random                    //> rng  : java.util.Random = java.util.Random@48533e64
3 
4 rng.nextInt                                       //> res0: Int = -1412360869
5 rng.nextInt                                       //> res1: Int = 645622520
6 
7 rng.nextDouble                                    //> res2: Double = 0.4216477872043267
8 rng.nextDouble                                    //> res3: Double = 2.306856098814869E-4

这个肯定不是泛函风格的RNG:同一个函数每次引用会产生不同的结果。泛函函数(pure function)的“等量替换”在这里不成立。再者,我们不难想象在以上rng里一定维护了一个状态,每次更新,产生了附带影响(side effect),这又违背了泛函纯函数(pure function)的不产生附带影响的要求(referencial transparency)。那么应该怎么办呢?泛函的做法重点在于用明确的方式来更新状态,即:不要维护内部状态,直接把新状态和结果一道返回,像下面这样:

1 trait RNG {
2   def nextInt: (Int, RNG)
3 }

从以上方式我们基本能得出泛函状态变迁(state transition)的款式:

假设我们有这么个类型结构:

1 class Foo {
2   var s: FooState = ...
3   def bar: Bar
4   def baz: Int
5 }

如果 bar 和 baz 会改变 Foo 的状态,那么我们应该这样设计bar, baz 函数:

1 trait Foo {
2   def bar: (Bar, Foo)
3   def baz: (Int, Foo)
4 }

好,那么我们试试设计泛函式的随意数产生器RNG:

 1 trait RNG {
 2     def nextInt: (Int, RNG)
 3 }
 4 //起始状态RNG, 种子RNG
 5 case class seedRNG(seed: Long) extends RNG {
 6     def nextInt: (Int, RNG) = {
 7      val seed2 = (seed*0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)
 8      ((seed2 >>> 16).asInstanceOf[Int], seedRNG(seed2))
 9     }
10 }
11 val rng = seedRNG(System.currentTimeMillis)       //> rng  : ch6.rng.seedRNG = seedRNG(1427201377395)
12 val (i,rng2) = rng.nextInt                        //> i  : Int = 1516062234
13                                                   //| rng2  : ch6.rng.RNG = seedRNG(99356654630658)
14 val (i2,rng3) = rng2.nextInt                      //> i2  : Int = 483165502
15                                                   //| rng3  : ch6.rng.RNG = seedRNG(31664734402533)
16 val (i3,rng4) = rng2.nextInt                      //> i3  : Int = 483165502
17                                                   //| rng4  : ch6.rng.RNG = seedRNG(31664734402533)

函数nextInt返回了一个随意数及新的RNG。如果我们使用同一个RNG产生的结果是一样的r2==r3,恰恰体现了泛函风格。

所有类型的泛函式随意数产生器都可以从Int RNG nextInt推导出来:

 1 object RNG {
 2   //值在 0.0 - 1.0 之间的Double随意数
 3     def nextDouble(rng: RNG): (Double, RNG) = {
 4         val (i,rng2) = rng.nextInt
 5         if ( i == Int.MaxValue ) (0.0, rng2)
 6         else ( i.toDouble / Int.MaxValue.toDouble, rng2)
 7     }
 8     def nextPositiveInt(rng: RNG): (Int, RNG) =  {
 9         val (i, rng2) = rng.nextInt
10         if ( i == Int.MaxValue ) (Int.MaxValue, rng2)
11         else (i.abs, rng2)
12     }
13     def nextBoolean(rng: RNG): (Boolean, RNG) = {
14         rng.nextInt match {
15             case (i, rng2) => (i % 2 == 0, rng2)
16         }
17     }
18     //产生一个随意tuple (Int, Double)
19     def nextIntDouble(rng: RNG): ((Int, Double), RNG) = {
20         val (i,rng2) = nextPositiveInt(rng)
21         val (d,rng3) = nextDouble(rng2)
22         ((i,d),rng3)
23     }
24     //产生一个随意数的n长度List
25     def nextInts(n: Int)(rng: RNG): (List[Int], RNG) = {
26         def go(n: Int, rng: RNG, acc: List[Int]): (List[Int], RNG) = {
27              if ( n <= 0 ) (acc, rng)
28              else {
29                  val (i,rng2) = rng.nextInt
30               go(n-1,rng2,i :: acc)
31              }
32         }
33         go(n,rng,Nil: List[Int])
34     }
35 }
36 import RNG._
37 
38 val rng = seedRNG(System.currentTimeMillis)       //> rng  : ch6.rng.seedRNG = seedRNG(1427204725766)
39 val (d, rng5) = nextDouble(rng)                   //> d  : Double = 0.6090536781628866
40                                                   //| rng5  : ch6.rng.RNG = seedRNG(85716684903065)
41 val (b, rng6) = nextBoolean(rng5)                 //> b  : Boolean = false
42                                                   //| rng6  : ch6.rng.RNG = seedRNG(123054239736112)
43 val ((i5,d2), rng7) = nextIntDouble(rng6)         //> i5  : Int = 1054924659
44                                                   //| d2  : Double = 0.8877875771782303
45                                                   //| rng7  : ch6.rng.RNG = seedRNG(124944993788778)
46 val (ints, rng8) = nextInts(5)(rng7)              //> ints  : List[Int] = List(-782449771, -1992066525, -825651621, -440562357, 7
47                                                   //| 00809062)
48                                                   //| rng8  : ch6.rng.RNG = seedRNG(230196348539649)

从以上的例子中可以发现这些函数一致的款式:func(RNG):(A,RNG),即:RNG => (A,RNG), 是lambda function,纯纯的函数类型申明。这样看来随意数产生器就是一个函数类型,我们可以把产生器当作函数的参数或者返回值来使用。那么我们可以自创一个新的类型:

1     type Rand[+A] = RNG => (A, RNG)

Rand就是一个随意数产生器,我们是可以把它传来传去的。那么下面我们就试着使用Rand类型:

 1 type Rand[+A] = RNG => (A, RNG)
 2     
 3     def rnInt: Rand[Int] = _.nextInt
 4     def rnPositiveInt: Rand[Int] = nextPositiveInt
 5 }
 6 import RNG._
 7 
 8 val rng = seedRNG(System.currentTimeMillis)       //> rng  : ch6.rng.seedRNG = seedRNG(1427239224137)
 9 rnInt(rng)                                        //> res0: (Int, ch6.rng.RNG) = (-1225681606,seedRNG(201148706995232))
10 rnPositiveInt(rng)                                //> res1: (Int, ch6.rng.RNG) = (1225681606,seedRNG(201148706995232))

在以上例子里我们可能注意到了一些别扭的东西:函数申明 def rnInt: Rand[Int] 好像没有参数,但使用时 rnInt(rng) 是需要参数的。不过如果我们想想 Func(RNG):(A,RNG) 的lambda表达形式 RNG => (A,RNG)自然就理解了。

既然我们已经把随意数产生器变成了Rand类型,我们应该可以方便地对随意数产生器进行组合、变形了吧?先看一个最基本的组件(combinator):

1     def unit[A](a: A): Rand[A] = {
2         rng => (a, rng)
3     }

乍看起来这个unit好像没什么用,没做什么事。实际上unit可以说是函数组合的最基本组件,是大大的有用的。unit只有一个作用:把a包进高阶类Rand里,换句话说就是把低阶类A升格到高阶Rand,这样就可以和其它Rand进行组合或者使用Rand函数自我变形了。这个简单的例子再次提示了从返回类型来推导功能实现这种泛函编程风格:Band[A] >>> RNG => (A, RNG) 即:给我一个RNG我就可以返回一个(A, RNG)。

再来一个针对Rand类型的map:

1     def map[A,B](ra: Rand[A])(f: A => B): Rand[B] = {
2       rng => {
3                 val (x, rng2) = ra(rng)
4                 (f(x), rng2) 
5         }

从以上函数的实现方式可以得出map就是对一个随意数产生器的结果进行转换后仍然保留Rand的高阶类型格式。还和上一个例子一样:我们一看到返回类型Rand就应该立刻想到 rng => {...(a2, rng2)}这种实现风格了。

举出个使用map的例子:

1     def rnDouble: Rand[Double] = { map(rnPositiveInt){ _ / (Int.MaxValue.toDouble + 1) } }
2 val rng = seedRNG(System.currentTimeMillis)       //> rng  : ch6.rng.seedRNG = seedRNG(1427245671833)
3 rnDouble(rng)                                     //> res0: (Double, ch6.rng.RNG) = (0.6156660546548665,seedRNG(86647294261296))

真够简洁的。下面再试着结合两个Rand:

1     def map2[A,B,C](ra: Rand[A], rb: Rand[B])(f: (A,B) => C): Rand[C] = {
2         rng => {
3             val (x,rng2) = ra(rng)
4             val (y,rng3) = rb(rng2)
5             (f(x,y), rng3)
6         }
7     }

真够简洁的。下面再试着结合两个Rand:

1     def map2[A,B,C](ra: Rand[A], rb: Rand[B])(f: (A,B) => C): Rand[C] = {
2         rng => {
3             val (x,rng2) = ra(rng)
4             val (y,rng3) = rb(rng2)
5             (f(x,y), rng3)
6         }
7     }

写几个使用map2的例子:

 1     def rnPair[A,B](ra: Rand[A], rb: Rand[B]): Rand[(A, B)] = {
 2         map2(ra,rb){(_,_)}
 3     }
 4     def rnIntDoublePair: Rand[(Int, Double)] = {
 5         rnPair(rnInt,rnDouble)
 6     }
 7     def rnDoubleIntPair: Rand[(Double, Int)] = {
 8         rnPair(rnDouble,rnInt)
 9     }
10 }
11 import RNG._
12 
13 val rng = seedRNG(System.currentTimeMillis)       //> rng  : ch6.rng.seedRNG = seedRNG(1427246457588)
14 rnIntDoublePair(rng)                              //> res0: ((Int, Double), ch6.rng.RNG) = ((-1302173232,0.355998701415956),seedR
15                                                   //| NG(231372613633230))
16 rnDoubleIntPair(rng)                              //> res1: ((Double, Int), ch6.rng.RNG) = ((0.6063716635107994,-764501390),seedR
17                                                   //| NG(231372613633230))

既然我们能用map2来结合两个Rand,那么能不能把一个List里面的Rand结合成一个Rand呢?

 1     //用递归方式
 2     def sequence[A](lr: List[Rand[A]]): Rand[List[A]] = {
 3       rng => {
 4           def go(xs: List[Rand[A]], r: RNG, acc: List[A]): (List[A], RNG) = {
 5               lr match {
 6                     case Nil => (acc,rng)
 7                     case h :: t => {
 8                         val (x, rng2) = h(rng)
 9             go(t,rng2,x::acc)
10                   }
11               }
12           }
13           go(lr,rng,List())
14         }
15     }
16     //用foldRight实现
17     def sequence_1[A](lr: List[Rand[A]]): Rand[List[A]] = {
18        lr.foldRight(unit(Nil: List[A])) {(h,t) => map2(h,t)(_ :: _)}
19     }

从以上foldRight实现方式可以体会unit的作用:它把List[A]升了格,这样才能与Rand的map2类型匹配。可以发现使用了map,map2,sequence去操作Rand时,我们已经无须理会这个RNG了,这证明我们已经向着更高的抽象层进步了,这也是泛函编程的真义所在。但是光靠map,map2,sequence就可以办成所有的事了吗?不是!想想那个正整数随意数产生器positiveInt,如果用rnInt产生了Int.MinValue的话就重新再产生一个,直到产生出一个不为Int.MinValue的数。我们试着用map来实现:

1 def positiveInt: Rand[Int] = {
2   map(int) { i =>
3     if (i != Int.MinValue) i.abs else ??
4   }
5 }

map的操作函数类型是f: A => B,重复运算positiveInt返回类型是Rand[A], 不匹配,我们就卡在这了。但再看看这个问题可以用flatMap解决:因为flatMap的操作函数f: A => Rand[B], 类型是匹配的。我们可以用unit把 i.abs升格就可以使用flatMap解决问题了。

赶快实现flatMap:

 1     def flatMap[A,B](ra: Rand[A])(f: A => Rand[B]): Rand[B] = {
 2         rng => {
 3             val (x, rng2) = ra(rng)
 4             f(x)(rng2)
 5         }
 6     }
 7     def positiveIntByFlatMap: Rand[Int] = {
 8         flatMap(rnInt) {
 9             a => {
10                 if ( a != Int.MinValue) unit(a.abs)
11                 else positiveIntByFlatMap
12             }
13         }
14     }

没错,可以用flatMap实现positiveInt了。那么用flatMap可以实现map,map2吗?看看下面的具体实现方法:

1   def mapByFlatMap[A,B](ra: Rand[A])(f: A => B): Rand[B] = {
2       flatMap(ra){ a => unit(f(a)) }
3   }
4   def map2ByFlatMap[A,B,C](ra: Rand[A], rb: Rand[B])(f: (A,B) => C): Rand[C] = {
5         flatMap(ra){ a => map(rb) {b => f(a,b)}}
6   }
7   def map3ByFlatMap[A,B,C,D](ra: Rand[A], rb: Rand[B], rc: Rand[C])(f: (A,B,C) => D): Rand[D] = {
8         flatMap(ra){ a => flatMap(rb) {b => map(rc) {c => f(a,b,c)}}}
9   }

看,代码是不是越来越简洁了?而且仿佛进入了数学世界。我是说现在感觉编程已经变成了好像高中做数学题一样:拿到一个函数描述就开始想办法用什么其它现有的函数来解决;然后匹配一下类型,找找以前的例子,等等。。。,完全没有感觉到是在编写计算机程序。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java技术栈

跟我学 Java 8 新特性之 Stream 流(六)收集

我们前面的五篇文章基本都是在说将一个集合转成一个流,然后对流进行操作,其实这种操作是最多的,但有时候我们也是需要从流中收集起一些元素,并以集合的方式返回,我们把...

992
来自专栏向治洪

ViewPager 实现 Galler 效果, 中间大图显示,两边小图展示

正常情况下, ViewPager 一页只能显示一项数据, 但是我们常常看到网上,特别是电视机顶盒的首页经常出现中间大图显示两端也都露出一点来,这种效果怎么实现呢...

4765
来自专栏Java爬坑系列

【JAVA零基础入门系列】Day14 Java对象的克隆

  今天要介绍一个概念,对象的克隆。本篇有一定难度,请先做好心理准备。看不懂的话可以多看两遍,还是不懂的话,可以在下方留言,我会看情况进行修改和补充。   克隆...

1856
来自专栏Netkiller

GSON 多层Map剥离

工作中遇到一个问题,我们提供给外包方的 json 无法Decode 。 一段简单 JSON 字符串,字符串如下。 String json= "{\"0\":{...

2724
来自专栏恰同学骚年

C# 中的委托和事件

文中代码在VS2005下通过,由于VS2003(.Net Framework 1.1)不支持隐式的委托变量,所以如果在一个接受委托类型的位置直接赋予方法名,...

752
来自专栏函数式编程语言及工具

Akka(24): Stream:从外部系统控制数据流-control live stream from external system

 在数据流应用的现实场景中常常会遇到与外界系统对接的需求。这些外部系统可能是Actor系统又或者是一些其它类型的系统。与这些外界系统对接的意思是在另一个线程...

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

java:POI导出excel

POI是一个开源项目,专用于java平台上操作MS OFFICE,企业应用开发中可用它方便导出Excel. 下面是使用示例: 1、maven中先添加依赖项 1 ...

2175
来自专栏Android知识点总结

Java容器源码攻坚战--第三战:HashMap(一)

HashMap怪复杂的,如果一开始就上网上一大堆的HashMap的元素图,也没什么太大意思。 这里从一个小测试开始说起,一步步debug在HashMap里走一...

705
来自专栏柠檬先生

python 基础 切片 迭代 列表生成式

对list 进行切片   如列表     L = ['Adam', 'Lisa', 'Bart', 'Paul']     L[0:3]     ['Adam'...

37910
来自专栏mukekeheart的iOS之旅

判断两个单链表是否相交(有环、无环两种)

题目描述:   给定两个单链表的头节点head1和head2,如何判断两个链表是否相交?相交的话返回true,不想交的话返回false。   给定两个链表的头结...

2397

扫码关注云+社区