Монадный подход к оценке ПИ в скале - PullRequest
Новая
       23

Монадный подход к оценке ПИ в скале

2 голосов
/ 16 апреля 2019

Я пытаюсь понять, как использовать монады в scala для решения простых задач как способ укрепления моего знакомства. Одной простой проблемой является оценка PI с использованием функционального генератора случайных чисел. Я включил приведенный ниже код для простого потокового подхода.

Я ищу помощи в переводе этого на монадический подход. Например, есть ли идиоматический способ преобразования этого кода в использование состояния (и других монад) безопасным для стека способом? 

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

Я подозреваю, что я ищу что-то вроде replicateM из монады Applicative у кошек, но я не уверен, как выстроить типы или как это сделать так, чтобы не накапливать промежуточные результаты в памяти. Или есть способ сделать это с for пониманием, которое может итеративно создавать Point s?

Ответы [ 2 ]

5 голосов
/ 16 апреля 2019

Если вы хотите итерировать использование монады безопасным для стека способом, то в классе типов 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)

Он использует параметр по имени, потому что вы можетепопробуйте передать что-то вроде Future (даже если Future не законно), которые стремятся, так что вам придется снова и снова оценивать одно и то же.По крайней мере, по имени param у вас есть шанс передать рецепт случайного побочного эффекта.Конечно, если мы используем Option, List в качестве монады, содержащей наше «случайное» число, мы также должны ожидать забавных результатов.

Правильное решение будет использовать что-то, что гарантирует, что F[A]лениво оценивается, и любой побочный эффект внутри оценивается каждый раз, когда вам нужно значение изнутри.Для этого вам в основном нужно использовать некоторые классы типов эффектов, например, 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
}
0 голосов
/ 17 апреля 2019

Вот еще один подход, который придумал мой друг Чарльз Миллер . Он немного более прямой, так как он использует RNG напрямую, но использует тот же подход, что и @Mateusz Kubuszok, который использует Monad.

Ключевым отличием является то, что он использует монаду State, поэтому мы можем продвигать состояние RNG через вычисления и генерировать случайные числа, используя «чистый» генератор случайных чисел. 

import cats._
import cats.data._
import cats.implicits._

object PICharles {
  type RNG[A] = State[Long, A]

  object RNG {
    def nextLong: RNG[Long] =
      State.modify[Long](
        seed ⇒ (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL
      ) >> State.get

    def nextInt: RNG[Int] = nextLong.map(l ⇒ (l >>> 16).toInt)

    def nextNatural: RNG[Int] = nextInt.map { i ⇒
      if (i > 0) i
      else if (i == Int.MinValue) 0
      else i + Int.MaxValue
    }

    def nextDouble: RNG[Double] = nextNatural.map(_.toDouble / Int.MaxValue)

    def runRng[A](seed: Long)(rng: RNG[A]): A = rng.runA(seed).value

    def unsafeRunRng[A]: RNG[A] ⇒ A = runRng(System.currentTimeMillis)
  }

  object PI {
    case class Step(count: Int, inCircle: Int)

    def calculatePi(iterations: Int): RNG[Double] = {
      def step(s: Step): RNG[Either[Step, Double]] =
        for {
          x ← RNG.nextDouble
          y ← RNG.nextDouble
          isInCircle = (x * x + y * y) < 1.0
          newInCircle = s.inCircle + (if (isInCircle) 1 else 0)
        } yield {
          if (s.count >= iterations)
            Right(s.inCircle.toDouble / s.count.toDouble * 4.0)
          else
            Left(Step(s.count + 1, newInCircle))
        }

      Monad[RNG].tailRecM(Step(0, 0))(step(_))
    }

    def unsafeCalculatePi(iterations: Int) =
      RNG.unsafeRunRng(calculatePi(iterations))
  }
}

Спасибо Charles & Mateusz за вашу помощь!

...