为什么`Random.nextInt`被认为不是'可组合的,模块化的,易于并行化'

Question

从"Scala中的函数式编程"一书中,有一节介绍如何以函数方式编写随机数生成器.

它给出了一个例子scala.util.Random:

即使我们对scala.util.Random中发生的事情一无所知,我们也可以假设对象rng有一些在每次调用后都会更新的内部状态,因为每次调用nextInt时我们都会得到相同的值.或者nextDouble.由于状态更新是作为副作用执行的,因此这些方法不是引用透明的.而且正如我们所知,这意味着它们不是可测试的,可组合的,模块化的,并且可以很容易地并行化.

最后一句,它说不是:

1. 可测试
2. 可组合
3. 模块化
4. 容易并行化

在后面的内容中,它解释了testable部分,但如何理解其他3个方面？

Answer 1

1.可测试

您无法轻易隔离其状态,尤其是在测试并行运行时.这使得在并行运行测试时不可能以可预测的方式再现一系列随机数.

2.可组合

您无法构建一系列操作,这些操作首先使用已知值为随机数播种,然后获取关于此种子的序列(特别是在并行运行时).

虽然这可能与"可测试"重叠,但出于安全原因,它可能也是必要的,因此您不会意外地将状态从一个会话泄漏到另一个会话.

3.模块化

没有办法交换不同的随机化算法.所有模块都必须使用相同的算法.这与"可组合"重叠,在某种意义上,您不能将生成器作为(可能是隐式)参数提供,而不是种子.

4.并行化

所有线程只有一种状态.在高度并发的情况下,这可能是一个严重的瓶颈.

一些示例代码

请不要在生产中使用此代码.它非常笨拙,有了scalaz或猫你可以轻松地建立更好的东西.通常,随机数生成器是一个comonad,它的状态是monad.

首先,让我们通过提供不同的伪随机生成器和不同的种子来使代码模块化

// This is a commonly used pseudo-random generator
// https://en.wikipedia.org/wiki/Linear_congruential_generator
// This implementation is awful slow!
def lcg(multiplier : BigInt, increment : BigInt, dividend : BigInt)(seed : BigInt) =
  (seed * multiplier + increment) mod dividend

// Some commonly used pseudo random number generators
def glibRand = lcg(multiplier = 1103515245,   increment = 12345,   dividend = 2^31) _
def vb6Rand  = lcg(multiplier = 214013,       increment = 2531011, dividend = 2^31) _
def javaRand = lcg(multiplier = 25214903917L, increment = 11,      dividend = 2L^48) _


// This is really insecure, don't use it for anything serious!
def seedFromTime() = BigInt(System.nanoTime())

// I used a dice to determine this value, so it's random!
def randomSeed = 5 

然后让我们构建一个可以组成函数的实现:

case class Random[T,U](val generator : T => T, val seed : T)(val currentValue : U){
 def apply[V](f : (T,U) => V) : Random[T,V] = {
   val nextRandom = generator(seed)
   Random(generator, nextRandom)(f(nextRandom, currentValue))
  }

  def unsafeGetValue = currentValue
}

我们使用这个构建块生成一个随机数列表并总结一些随机数的几个例子:

val randomNumbers  = Stream.iterate(Random(glibRand, seedFromTime())(List.empty[BigInt])){r : Random[BigInt, List[BigInt]] =>
  r.apply{(rnd : BigInt, numbers : List[BigInt]) =>
    rnd :: numbers
  }
}

randomNumbers.take(10).last.unsafeGetValue

val randomSum = Stream.iterate(Random(glibRand, seedFromTime())(BigInt(0))) { r: Random[BigInt, BigInt] =>
  r.apply(_ + _)
}

randomSum.take(100).last.unsafeGetValue

像往常一样,当我们想要用函数式语言编写某些东西时,我们将编写函数来实现不同的目标.如果我们提供了monadic实现,我们也可以将函数与副作用结合起来.

在这种情况下,并行化和可测试性会自动跟随(像往常一样).