了解Scala中的随机Monad [英] Understanding Random monad in Scala

问题描述

这是我之前的问题的后续操作

特拉维斯·布朗指出，java.util.Random具有副作用，并建议使用随机monad Rng 库，以使代码具有纯粹的功能.现在，我正在尝试自己构建一个简化的随机monad，以了解其工作原理.

这有意义吗?您将如何解决/改进以下说明?

随机生成器

首先，我们抄袭java.util.Random

中的随机生成函数

 // do some bit magic to generate a new random "seed" from the given "seed" 
 // and return both the new "seed" and a random value based on it

 def next(seed: Long, bits: Int): (Long, Int) = ...

请注意，next都返回 both 新的种子和值，而不仅仅是返回值.我们需要它来将新的种子传递给另一个函数调用.

随机点

现在让我们编写一个函数以在单位正方形中生成随机点.

假设我们有一个函数可以生成范围为[0，1]的随机double

 def randomDouble(seed: Long): (Long, Double) = ... // some bit magic

现在我们可以编写一个函数来生成随机点.

def randomPoint(seed: Long): (Long, (Double, Double)) = {
   val (seed1, x) = randomDouble(seed)
   val (seed2, y) = randomDouble(seed1)
   (seed2, (x, y)) 
}

到目前为止，一切都很好，并且randomDouble和randomPoint都是纯净的.唯一的问题是我们编写了randomDouble来构建randomPoint ad .我们没有 generic 工具来组合产生随机值的函数.

Monad 随机

现在，我们将定义一个 generic 工具，以构成产生随机值的函数.首先，我们概括randomDouble的类型:

type Random[A] = Long => (Long, A) // generate a random value of type A

，然后围绕它构建一个包装器类.

class Random[A](run: Long => (Long, A))

我们需要包装器来定义flatMap(在Haskell中为 bind )和 for-comprehension 使用的map方法.

class Random[A](run: Long => (Long, A)) {
  def apply(seed: Long) = run(seed)  

  def flatMap[B](f: A => Random[B]): Random[B] =
    new Random({seed: Long => val (seed1, a) = run(seed); f(a)(seed1)})

  def map[B](f: A => B): Random[B] =
    new Random({seed: Long = val (seed1, a) = run(seed); (seed1, f(a))})
}  

现在，我们添加一个 factory 函数来创建一个琐碎的Random[A](顺便说一句，它绝对是确定性的，而不是随机的")这是一个 return 函数(在Haskell中为 return ).

def certain[A](a: A) = new Random({seed: Long => (seed, a)})

Random[A]是产生类型A随机值的计算.方法flatMap，map和函数unit用于进行组成简单计算建立更复杂的.例如，我们将组成两个Random[Double]来构建Random[(Double, Double)].

单子随机点

现在，当我们有单子时，我们准备重新访问randomPoint和randomDouble.现在，我们将它们分别定义为产生Random[Double]和Random[(Double, Double)]

的函数

def randomDouble(): Random[Double] = new Random({seed: Long => ... })
def randomPoint(): Random[(Double, Double)] =
  randomDouble().flatMap(x => randomDouble().flatMap(y => certain(x, y))

此实现比上一个实现更好，因为它使用了通用工具(flatMap和certain)来编写两个Random[Double]调用并进行构建Random[(Double, Double)].

现在可以重新使用此工具来构建更多的函数来生成随机值.

Pi的蒙特卡洛计算

现在，我们可以使用map来测试圆中是否有随机点:

def randomCircleTest(): Random[Boolean] = 
  randomPoint().map {case (x, y) => x * x + y * y <= 1} 

我们还可以根据Random[A]

定义蒙特卡洛模拟

def monteCarlo(test: Random[Boolean], trials: Int): Random[Double] = ...

最后是计算PI的函数

def pi(trials: Int): Random[Double] = ....

所有这些功能都是纯函数.只有当我们最终应用pi函数以获取pi的值时，副作用才会发生.

解决方案

尽管有点复杂，但是您的方法还是不错的.我还建议您看一下 Scala中的函数编程的第6章. 和 Runar Bjarnason . 本章称为纯函数状态，它展示了如何创建纯函数随机生成器并在其之上定义其数据类型代数以提供全功能组合支持.

This a follow-up to my previous question

Travis Brown pointed out that java.util.Random is side-effecting and suggested a random monad Rng library to make the code purely functional. Now I am trying to build a simplified random monad by myself to understand how it works.

Does it make sense ? How would you fix/improve the explanation below ?

Random Generator

First we plagiarize a random generating function from java.util.Random

 // do some bit magic to generate a new random "seed" from the given "seed" 
 // and return both the new "seed" and a random value based on it

 def next(seed: Long, bits: Int): (Long, Int) = ...

Note that next returns both the new seed and the value rather than just the value. We need it to pass the new seed to another function invocation.

Random Point

Now let's write a function to generate a random point in a unit square.

Suppose we have a function to generate a random double in range [0, 1]

 def randomDouble(seed: Long): (Long, Double) = ... // some bit magic

Now we can write a function to generate a random point.

def randomPoint(seed: Long): (Long, (Double, Double)) = {
   val (seed1, x) = randomDouble(seed)
   val (seed2, y) = randomDouble(seed1)
   (seed2, (x, y)) 
}

So far, so good and both randomDouble and randomPoint are pure. The only problem is that we compose randomDouble to build randomPoint ad hoc. We don't have a generic tool to compose functions yielding random values.

Monad Random

Now we will define a generic tool to compose functions yielding random values. First, we generalize the type of randomDouble:

type Random[A] = Long => (Long, A) // generate a random value of type A

and then build a wrapper class around it.

class Random[A](run: Long => (Long, A))

We need the wrapper to define methods flatMap (as bind in Haskell) and map used by for-comprehension.

class Random[A](run: Long => (Long, A)) {
  def apply(seed: Long) = run(seed)  

  def flatMap[B](f: A => Random[B]): Random[B] =
    new Random({seed: Long => val (seed1, a) = run(seed); f(a)(seed1)})

  def map[B](f: A => B): Random[B] =
    new Random({seed: Long = val (seed1, a) = run(seed); (seed1, f(a))})
}  

Now we add a factory-function to create a trivial Random[A] (which is absolutely deterministic rather than "random", by the way) This is a return function (as return in Haskell).

def certain[A](a: A) = new Random({seed: Long => (seed, a)})

Random[A] is a computation yielding random value of type A. The methods flatMap , map, and function unit serves for composing simple computations to build more complex ones. For example, we will compose two Random[Double] to build Random[(Double, Double)].

Monadic Random Point

Now when we have a monad we are ready to revisit randomPoint and randomDouble. Now we define them differently as functions yielding Random[Double] and Random[(Double, Double)]

def randomDouble(): Random[Double] = new Random({seed: Long => ... })
def randomPoint(): Random[(Double, Double)] =
  randomDouble().flatMap(x => randomDouble().flatMap(y => certain(x, y))

This implementation is better than the previous one since it uses a generic tool (flatMap and certain) to compose two calls of Random[Double] and build Random[(Double, Double)].

Now can re-use this tool to build more functions generating random values.

Monte-Carlo calculation of Pi

Now we can use map to test if a random point is in the circle:

def randomCircleTest(): Random[Boolean] = 
  randomPoint().map {case (x, y) => x * x + y * y <= 1} 

We can also define a Monte-Carlo simulation in terms of Random[A]

def monteCarlo(test: Random[Boolean], trials: Int): Random[Double] = ...

and finally the function to calculate PI

def pi(trials: Int): Random[Double] = ....

All those functions are pure. Side-effects occur only when we finally apply the pi function to get the value of pi.

解决方案

Your approach is quite nice although it is a little bit complicated. I also suggested you to take a look at Chapter 6 of Functional Programming in Scala By Paul Chiusano and Runar Bjarnason. The chapter is called Purely Functional State and it shows how to create purely functional random generator and define its data type algebra on top of that to have full function composition support.

这篇关于了解Scala中的随机Monad的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！