如何使用功能状态生成随机数？

Question

我正在努力弄清楚如何将State的函数表示与Scala的Random类合并以生成随机整数.我正在学习Scala中的函数编程一书,因此大部分代码都是从那里获取的.

以下是State类的外观,直接来自本书:

case class State[S, +A](run: S => (A, S))

这就是我想要做的事情:

object State {
  type Rand[A] = State[A, Random] // the Random from scala.util.Random

  def nextIntInRange(from: Int, to: Int): Rand[Int] =
  ??? _.nextInt(from - to) + from ??? // unsure about much of this

  def get(a: Rand[A]): A = ??? // also unsure; should modify state

  def getAndPreserveState(a: Rand[A]): A = ??? // ditto; should not modify state

  def diceRolls(n: Int) = {
    val roll = nextIntInRange(1, 6) 
    go(n: Int, acc: List[Int]): List[Int] = {
      if (n >= 0) go(n-1, get(roll) :: acc) else acc
    }
    go(n, List())
  }

我花了好几个小时试图弄清楚如何使用State的构造函数,并且尚未实现我想要的东西,因此几乎完全缺乏对如何实现前三种方法的理解.

我的目标是能够将diceRolls与任何大小的整数和任何给定的起始种子一起使用,并生成一个永不改变的整数列表.换句话说,diceRolls(3)可能是List(3,3,2),如果是的话,重写它diceRolls(7).take(3)必须再次产生List(3,3,2),等等.

Answer 1

我们想要生成随机数并将随机数生成器(现在是RNG)(类型scala.util.Random)保持为State类中的状态.

我们可以将类型定义Rand[A]为:

type Rand[A] = State[Random, A]

我们希望能够获得范围内的随机整数.如果我们有RNG,可以使用以下方法轻松完成:

def randomInRange(rng: Random, start: Int, end: Int) = 
  rng.nextInt(end - start + 1) + start

randomInRange(new Random(1L), 10, 20) // Int = 14

但是我们想要使用先前状态的RNG,因此我们State在run函数中定义了相同的代码:

def nextIntInRange(from: Int, to: Int): Rand[Int] = 
  State((r: Random) => (r.nextInt(to - from + 1) + from, r))

我们的nextIntInRange函数返回一个随机数和RNG.让我们定义roll测试它:

val roll = nextIntInRange(1, 6)

val rng = new Random(1L)
val (one, rng2) = roll.run(rng)
// (Int, scala.util.Random) = (4,scala.util.Random@5fb84db9)
val (two, rng3) = roll.run(rng2)
// (Int, scala.util.Random) = (5,scala.util.Random@5fb84db9)

到目前为止,我们可能会想到这么好,但如果我们使用rng两次,我们希望收到相同的随机数:

val rng = new Random(1L)
val (one, _) = roll.run(rng) // 4
val (two, _) = roll.run(rng) // 5

我们得到两个不同的数字,这不是我们使用时想要的数字State.我们希望使用相同RNG的滚动返回相同的结果.问题是它Random改变了它的内部状态,所以我们不能把后续的状态改变State.

在Scala中的函数式编程中,通过定义一个新的随机数生成器来解决这个问题,该生成器也将其返回状态nextInt.

虽然使用Random失败了使用的目的State,但我们可以尝试将其余的功能作为教育练习来实现.

让我们来看看get和getAndPreserveState:

def get(a: Rand[A]): A = ??? // also unsure; should modify state

def getAndPreserveState(a: Rand[A]): A = ??? // ditto; should not modify state

如果我们查看类型签名,我们需要传递Rand[A]类似我们的roll函数并返回此函数的结果.由于以下几个原因,这些功能很奇怪:

• 我们的roll函数需要一个Random实例来获得结果,但是我们没有类型的参数Random.
• 返回类型是A,所以如果我们有一个Random实例,我们只能在调用后返回随机数a.run(ourRng),但我们应该如何处理我们的状态.我们希望明确地保持我们的状态.

让我们留下这些功能,他们试图摆脱我们宝贵的状态,并实现最终功能diceRolls,我们想要掷骰子几次并返回随机数列表.因此,这个功能的类型Rand[List[Int]].

我们已经有了一个函数roll,现在我们需要多次使用它,我们可以用它来做List.fill:

List.fill(10)(roll) // List[Rand[Int]] 

但是所产生的类型List[Rand[Int]],而不是Rand[List[Int]].转换F[G[_]]为G[F[_]]通常称为的操作sequence,让我们直接实现它 State:

object State {

  def sequence[A, S](xs: List[State[S, A]]): State[S, List[A]] = {
    def go[S, A](list: List[State[S, A]], accState: State[S, List[A]]): State[S, List[A]] = 
      list match { 
        // we have combined all States, lets reverse the accumulated list
        case Nil => 
          State((inputState: S) => {
            val (accList, state) = accState.run(inputState)
            (accList.reverse, state)
          })
        case stateTransf :: tail => 
          go(
            tail,
            State((inputState: S) => {
              // map2
              val (accList, oldState) = accState.run(inputState) 
              val (a, nextState) = stateTransf.run(oldState)
              (a :: accList, nextState) 
            })
          )
      }
    // unit
    go(xs, State((s: S) => (List.empty[A], s)))
  }

}

对我们案例的一些解释Rand[Int]:

// use the RNG in to create the previous random numbers
val (accList, oldState) = accState.run(inputState)
// generate a new random number 
val (a, nextState) = stateTransf.run(oldState)
// add the randomly generated number to the already generated random numbers
// and return the new state of the RNG
(a :: accList, nextState) 

State.sequence通过在github上的fpinscala答案中定义一个unit和一个map2函数,可以大大清理我的实现.

现在我们可以将我们的diceRolls函数定义为:

def diceRolls(n: Int) = State.sequence(List.fill(n)(roll))

我们可以用作:

diceRolls(5).run(new Random(1L))
// (List[Int], scala.util.Random) = (List(4, 5, 2, 4, 3),scala.util.Random@59b194af)