scala - 在 scala 中估计 PI 的单子(monad)方法

Question

我试图了解如何在 scala 中利用 monad 来解决简单的问题，以此来提高我的熟悉度。一个简单的问题是使用函数式随机数生成器来估算 PI。我在下面包含了一个简单的基于流的方法的代码。

我正在寻求帮助将其转化为单子(monad)方法。例如，是否有一种惯用的方法将此代码转换为以堆栈安全的方式使用状态(和其他 monad)？

trait RNG {
    def nextInt: (Int, RNG)
    def nextDouble: (Double, RNG)
}

case class Point(x: Double, y: Double) {
    val isInCircle = (x * x + y * y) < 1.0
}

object RNG {
    def nonNegativeInt(rng: RNG): (Int, RNG) = {
      val (ni, rng2) = rng.nextInt
      if (ni > 0) (ni, rng2)
      else if (ni == Int.MinValue) (0, rng2)
      else (ni + Int.MaxValue, rng2)
    }

    def double(rng: RNG): (Double, RNG) = {
      val (ni, rng2) = nonNegativeInt(rng)
      (ni.toDouble / Int.MaxValue, rng2)
    }


    case class Simple(seed: Long) extends RNG {
      def nextInt: (Int, RNG) = {
      val newSeed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL
      val nextRNG = Simple(newSeed)
      val n = (newSeed >>> 16).toInt
      (n, nextRNG)
    }

    def nextDouble: (Double, RNG) = {
      val (n, nextRNG) = nextInt
      double(nextRNG)
    }
  }
}

object PI {
    import RNG._

    def doubleStream(rng: Simple):Stream[Double] = rng.nextDouble match {
        case (d:Double, next:Simple) => d #:: doubleStream(next)
    }

    def estimate(rng: Simple, iter: Int): Double = {
        val doubles = doubleStream(rng).take(iter)
        val inside = (doubles zip doubles.drop(3))
            .map { case (a, b) => Point(a, b) }
            .filter(p => p.isInCircle)
            .size * 1.0
        (inside / iter) * 4.0
    }
}

// > PI.estimate(RNG.Simple(10), 100000)
// res1: Double = 3.14944

我怀疑我正在从猫的 Applicative monad 中寻找类似 replicateM 的东西，但我不确定如何排列类型或如何做以一种不会在内存中累积中间结果的方式。或者，有没有一种方法可以通过 for 理解来迭代构建 Point？

Answer 1

如果您想以堆栈安全的方式使用 monad 进行迭代，那么在 Monad 类型类中实现了一个 tailRecM 方法:

// assuming random generated [-1.0,1.0]
def calculatePi[F[_]](iterations: Int)
                     (random: => F[Double])
                     (implicit F: Monad[F]): F[Double] = {
  case class Iterations(total: Int, inCircle: Int)
  def step(data: Iterations): F[Either[Iterations, Double]] = for {
    x <- random
    y <- random
    isInCircle = (x * x + y * y) < 1.0
    newTotal = data.total + 1
    newInCircle = data.inCircle + (if (isInCircle) 1 else 0)
  } yield {
    if (newTotal >= iterations) Right(newInCircle.toDouble / newTotal.toDouble * 4.0)
    else Left(Iterations(newTotal, newInCircle))
  }
  // iterates until Right value is returned
  F.tailRecM(Iterations(0, 0))(step)
}
calculatePi(10000)(Future { Random.nextDouble }).onComplete(println)

它使用 by-name 参数，因为你可以尝试向那里传递类似 Future 的东西(即使 Future 是不合法的)，这是渴望的，所以你会最终一次又一次地评估同一件事。至少通过名称参数，您有机会向那里传递副作用随机的配方。当然，如果我们使用 Option、List 作为保存我们“随机”数字的 monad，我们也应该期待有趣的结果。

正确的解决方案是使用一些东西来确保这个 F[A] 被惰性求值，并且每次你需要从内部获取一个值时，内部的任何副作用都会被求值。为此，您基本上必须使用一些 Effects 类型类，例如Sync 来自 Cats Effects。

def calculatePi[F[_]](iterations: Int)
                     (random: F[Double])
                     (implicit F: Sync[F]): F[Double] = {
  ...
}
calculatePi(10000)(Coeval( Random.nextDouble )).value
calculatePi(10000)(Task( Random.nextDouble )).runAsync

或者，如果您不太关心纯度，则可以传递副作用函数或对象而不是 F[Int] 来生成随机数。

// simplified, hardcoded F=Coeval
def calculatePi(iterations: Int)
               (random: () => Double): Double = {
  case class Iterations(total: Int, inCircle: Int)
  def step(data: Iterations) = Coeval {
    val x = random()
    val y = random()
    val isInCircle = (x * x + y * y) < 1.0
    val newTotal = data.total + 1
    val newInCircle = data.inCircle + (if (isInCircle) 1 else 0)
    if (newTotal >= iterations) Right(newInCircle.toDouble / newTotal.toDouble * 4.0)
    else Left(Iterations(newTotal, newInCircle))
  }
  Monad[Coeval].tailRecM(Iterations(0, 0))(step).value
}