Generic Programming (15) - Generic States - Random Number Generator
aboutOOP For programmers， (math.) pan-functional state change（functional state transition） It's an unfamiliar subject.。 Generalized function state variation is achieved through the generalized function state data type（functional state） come round realize of。State is a type that appears in generic programming（type）。 As with other data types，State Again, it needs its own set of generic operators and combinatorial functions（combinators）， We will discuss in the following sections aboutState Design options for data types。
In a formal introductionState pre-type， Let's start with random number generator（RNG: Random Number Generator） commencement， From the general letterRNG The principle analysis of the leads toState Design solutions。
Let's start by looking at the familiar 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
This is certainly not a generic style RNG: the same function produces a different result each time it is referenced. The "equal substitution" of the pure function does not hold here. Further, it is not difficult to imagine that a state must be maintained in the above rng, and that each update, which produces a side effect, again violates the requirement of no collateral effect (referencial transparency) of the generalized pure function. So what should be done? The focus of the generic approach is to update the state in an explicit way, i.e., don't maintain the internal state and return the new state directly along with the result, like the following.
1 trait RNG {
2 def nextInt: (Int, RNG)
3 }From the above approach we can basically derive the style of generalized state transition (state transition).
Suppose we have this type structure.
1 class Foo {
2 var s: FooState = ...
3 def bar: Bar
4 def baz: Int
5 }If bar and baz change the state of Foo, then we should design the bar, baz function like this.
1 trait Foo {
2 def bar: (Bar, Foo)
3 def baz: (Int, Foo)
4 }OK, so let's try to design generalized random number generators RNG:.
1 trait RNG {
2 def nextInt: (Int, RNG)
3 }
4 // starting stateRNG, seedRNG
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)functionnextInt Returned a random number and the newRNG。 If we make usefulness the sameRNG The result is the samer2==r3， Aptly reflecting the panopticon style。
All types of generic functional random number generators can be derived from the Int RNG nextInt:.
1 object RNG {
2 // value at 0.0 - 1.0 inter-Double random number
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 // Generate a randomtuple (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 // Generate a random number ofn lengthList
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)The consistent style of these functions can be found in the examples above：func(RNG):(A,RNG)， i.e.：RNG => (A,RNG)， belambda function， Pure function type declaration。 it seems that random number A generator is a function type， We can use generators as arguments to functions or return values to make usefulness。 Then we can create a new type of our own：
1 type Rand[+A] = RNG => (A, RNG)
Rand Just a random number generator， We are allowed to pass it around。 So here's what we'll try to make usefulnessRand types：
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))
We may have noticed something twisted in the above example： Function declaration def rnInt: Rand[Int] It doesn't seem to have parameters， make usefulness time rnInt(rng) It takes parameters.。 But if we think about it. Func(RNG):(A,RNG) oflambda form of expression RNG => (A,RNG) Naturally, I understand.。
Now that we have put random number The generator becomesRand types， We should have easy access to the random number Generators are combined、 It's deformed, right?？ Let's start by looking at one of the most basic components（combinator）：
1 def unit[A](a: A): Rand[A] = {
2 rng => (a, rng)
3 }At first glance it looks like thisunit It doesn't seem like much. usefulness， Didn't do anything.。 in realityunit Arguably the most basic component of a function combination， It's a big yes. usefulness of。unit Only one work usefulness： classifier for objects with a handlea Inclusion in advanced classesRand Li (surname)， In other words take the lower order classesA Upgrading to higher levelsRand， This way it can be used with otherRand Make combinations or make usefulnessRand The function has deformed itself。 This simple example again hints at deriving functionality from the return type realize This style of general function programming：Band[A] >>> RNG => (A, RNG) i.e.： Give me one.RNG I can then return a(A, RNG)。
One more map for the Rand type.
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 }From the above function of realize The way it can be derivedmap It's the same thing that happens to a random number The result of the generator is converted and still retainedRand The higher-order type format of。 Still the same as the last example： As soon as we see the return typeRand One should immediately think of rng => {...(a2, rng2)} such realize Style up.。
Cite one that makes usefulnessmap examples of：
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))How concise. Try combining two more Rands below.
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 }How concise. Try combining two more Rands below.
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 }Write a few examples of using 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))Since we can usefulnessmap2 to combine twoRand， So can you put aList innerRand combined into oneRand this (Cantonese)？
1 // using recursive methods
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 // usefulnessfoldRight realize
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 }from the abovefoldRight realize The way you can experienceunit existing practice usefulness： it putsList[A］ Upgraded.， This is the only way to be associated withRand ofmap2 Type Matching。 It can be found that making usefulness finishmap,map2,sequence go ahead and operateRand time， We no longer need to bother with thisRNG finish， This proves that we have progressed to a higher level of abstraction， This is where the true meaning of generic programming comes in。 But on the basis ofmap,map2,sequence And that's all there is to do?？ not！ Think about that positive integer. random number generatorpositiveInt， in case usefulnessrnInt yieldInt.MinValue If you do, you will recreate a， Until it produces a product that is not forInt.MinValue numbers。 We tried. usefulnessmap come round realize：
1 def positiveInt: Rand[Int] = {
2 map(int) { i =>
3 if (i != Int.MinValue) i.abs else ??
4 }
5 }map The operation function type off: A => B， repetitive operationpositiveInt The return type isRand[A], mismatch， That's where we're stuck.。 But a second look at the issue can usefulnessflatMap settle (a dispute)： owing toflatMap The operation functions off: A => Rand[B], The types are matched。 We can usefulnessunit classifier for objects with a handle i.abs Upgrade can make usefulnessflatMap It's a problem。
Hurry up and implement 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 }Yes, it is possible to implement positiveInt with flatMap. So is it possible to implement map,map2 with flatMap? Take a look at the following concrete implementation.
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 }See, isn't the code getting cleaner? And it's as if you've entered the world of mathematics. I mean now it feels like programming has become like doing math problems in high school: get a function description and start trying to figure out what other existing functions to use; then match the types, look up previous examples, etc.. , it didn't feel like writing a computer program at all.
Recommended>>
1、Taiwan netizens hold first Failed News Photo Exhibition heres all the dark history of politicians
2、You may not have access to network resources please contact the administrator of this server to find out if you have access rights
3、What to expect in 2018
4、Is your personal information safe Learn if you dont want to get screwed
5、Zhang Shoucheng dies once discovered angel particle