How do I elegantly use a pure random number generator inside a recursive function?

Question

In my game dungeon generator made in Scala, I have a recursive function that generates a "tree-like" structure. It takes in a pure random number generator (RNG), and outputs a random tree and a new random number generator.

My issue is that because it's recursive, and every time my function branches out, I don't want to pass in the same RNG to both branches, so I have to keep an inner var inside my outer function.

An excerpt from my code:

  def generate(parameters: RandomBSPTreeParameters)(rng: RNG): (BSPTree, RNG) = {
    var varRng: RNG = rng

    def inner(size: Size, verticalSplit: Boolean): BSPTree = {

      def verticalBranch = {
        val leeway = size.height - parameters.minLeafEdgeLength.value * 2
        val (topHeightOffset, newRng) = RNG.nextPositiveInt(leeway)(varRng)
        varRng = newRng
        val topHeight = parameters.minLeafEdgeLength.value + topHeightOffset
        VerticalBranch(
          inner(Size(size.width, topHeight), verticalSplit = false),
          inner(Size(size.width, size.height - topHeight), verticalSplit = false)
        )
      }

      def horizontalBranch = {
        val leeway = size.width - parameters.minLeafEdgeLength.value * 2
        val (topWidthOffset, newRng) = RNG.nextPositiveInt(leeway)(varRng)
        varRng = newRng
        val leftWidth = parameters.minLeafEdgeLength.value + topWidthOffset
        HorizontalBranch(
          inner(Size(leftWidth, size.height), verticalSplit = true),
          inner(Size(size.width  - leftWidth, size.height), verticalSplit = true)
        )
      }

      def randomOrientationBranch = {
        val (splitVertically, newRng) = RNG.nextBoolean(varRng)
        varRng = newRng

        if (splitVertically)
          verticalBranch
        else
          horizontalBranch
      }

      if(size.surface > parameters.minLeafSurface)
        size.shape match {
          case Square if size.width > parameters.minLeafEdgeLength.value * 2 => randomOrientationBranch
          case SkewedHorizontally if size.width > parameters.minLeafEdgeLength.value * 2  => horizontalBranch
          case SkewedVertically if size.height > parameters.minLeafEdgeLength.value * 2 => verticalBranch
        }
      else Leaf(size)
    }


    val (firstSplitIsVertical, newRng) = RNG.nextBoolean(varRng)
    varRng = newRng

    val tree = inner(parameters.size, firstSplitIsVertical)
    (tree, varRng)
  }

Can somebody guide me in the right direction for eliminating the need to keep the var varRng: RNG in this function, and make it state-less.

dk14 dk14 · Accepted Answer · 2017-03-29T04:02:10

Firstly, even if you get rid of the var, your function is still going to be side-effectful. The reason for that is that nextPositiveInt has a side-effect of generating random number. Even if nextPositiveInt takes numbers from immutable pre-generated collection (so, no IO) it has to increment internal position counter every-time you call it.

Secondly, if numbers are "pure" random, which is not really possible, IMO, but let's say they're at least i.i.d (independently and identically distributed) - it doesn't make any sense to pass different generator to a different branch as even if you pass a same generator - random data between branches still wouldn't correlate. So you can just use same rng everywhere.

If it's not the case and we're talking about pseudo-randomness (that could auto-correlate potentially) with a different seed per every case, just pass rng as a parameter for your inner functions, like :

 def verticalBranch(vrng: RNG) = ...

I'd also notice that you're not really propagating rng through a left (or right branch) - you'd have two vars then lrng, rrng, which in its turn would mean that you don't need vars at all - they could be vals:

 val lRng = newRng()
 val rRng = newRng()

 def verticalBranch = {
    ...
    val (topHeightOffset, newRng) = RNG.nextPositiveInt(leeway)(lRng)
 }

 def horizontalBranch = {
    ...
    val (topHeightOffset, newRng) = RNG.nextPositiveInt(leeway)(rRng)
 }

How to encapsulate side-effects better?

You can represent lRng, rRng and other necessary generators as Iterators:

 val lRngGen = Iterator.continually(RNG.nextPositiveInt(rRng))

and use something like:

 case class Accumulator(size: Size, tree: BSPTree)

 val vert = (lRngGen zip rRngGen).foldLeft(Accumulator(parameters.size, emptyTree)(createNode)`

 def createNode(rng: (Int, Int), acc: Accumulator): Accumulator = {
    acc.size.shape match ...
 }

However, it requires to completely rethink/rewrite your code in terms of foldLeft instead of explicit recursion.

How do I elegantly use a pure random number generator inside a recursive function?

1 Answers