Как я могу реализовать перемешивание Фишера-Йейтса в Scala без побочных эффектов?

Question

Я хочу реализовать алгоритм Фишера-Йейтса (перемешивание массива на месте) без побочных эффектов, используя STArray для локальных эффектов мутации и функционального генератора случайных чисел

type RNG[A] = State[Seed,A]

чтобы получить случайные целые числа, необходимые для алгоритма.

У меня есть метод def intInRange(max: Int): RNG[Int] который я могу использовать для создания случайного Int в [0, не более).

Из Википедии:

To shuffle an array a of n elements (indices 0..n-1):
    for i from n − 1 downto 1 do
        j ← random integer such that 0 ≤ j ≤ i
        exchange a[j] and a[i]

Я полагаю, мне нужно сложить State с ST как-то, но это меня смущает. Нужен ли мне [S]StateT[ST[S,?],Seed,A]? Должен ли я переписать RNG использовать StateT также?

(Изменить) Я не хочу привлекать IO и я не хочу заменять Vector за STArray потому что перетасовка не будет выполнена на месте.

Я знаю, что здесь есть реализация на Haskell, но в настоящее время я не способен понять и перенести это в Scalaz. Но, может быть, вы можете?:)

Заранее спасибо.

Answer 1

Вот более или менее прямой перевод с версии на Haskell, на которую вы ссылаетесь, в которой используется изменяемая STArray, Скалаз STArray не имеет точного эквивалента listArray функция, так что я сделал один. В противном случае это простая транслитерация:

import scalaz._
import scalaz.effect.{ST, STArray}
import ST._
import State._
import syntax.traverse._
import std.list._

def shuffle[A:Manifest](xs: List[A]): RNG[List[A]] = {
  def newArray[S](n: Int, as: List[A]): ST[S, STArray[S, A]] =
    if (n <= 0) newArr(0, null.asInstanceOf[A])
    else for {
      r <- newArr[S,A](n, as.head)
      _ <- r.fill((_, a: A) => a, as.zipWithIndex.map(_.swap))
    } yield r
  for {
    seed <- get[Seed]
    n = xs.length
    r <- runST(new Forall[({type λ[σ] = ST[σ, RNG[List[A]]]})#λ] {
      def apply[S] = for {
        g <- newVar[S](seed)
        randomRST = (lo: Int, hi: Int) => for {
          p <- g.read.map(intInRange(hi - lo).apply)
          (a, sp) = p
          _ <- g.write(sp)
        } yield a + lo
        ar  <- newArray[S](n, xs)
        xsp <- Range(0, n).toList.traverseU { i => for {
          j  <- randomRST(i, n)
          vi <- ar read i
          vj <- ar read j
          _  <- ar.write(j, vi)
        } yield vj }
        genp <- g.read
      } yield put(genp).map(_ => xsp)
    })
  } yield r
}

Хотя асимптотика использования изменяемого массива может быть хорошей, обратите внимание, что постоянные факторы ST Монада в Скале довольно большая. Возможно, вам лучше сделать это в монолитном блоке, используя обычные изменяемые массивы. Общий shuffle Функция остается чистой, потому что все ваше изменяемое состояние является локальным.

Answer 2

У вас есть много вариантов. Один простой (но не очень принципиальный) вариант - поднять оба Rng а также ST операции в IO а затем работать с ними вместе там. Другой будет использовать как STRef[Long] и STArray В то же самое ST, Другой будет использовать State[(Long, Vector[A]), ?],

Вы также можете использовать StateT[State[Long, ?], Vector[A], ?] но это было бы бессмысленно. Вы могли бы, вероятно, использовать StateT (для состояния ГСЧ) в течение ST (для массива), но опять же, я не вижу смысла.

Это можно сделать довольно чисто без побочных эффектов, просто Rng, хоть. Например, используя библиотеку NNTA RNG:

import com.nicta.rng._, scalaz._, Scalaz._

def shuffle[A](xs: Vector[A]): Rng[Vector[A]] =
  (xs.size - 1 to 1 by -1).toVector.traverseU(
    i => Rng.chooseint(0, i).map((i, _))
  ).map {
    _.foldLeft(xs) {
      case ((i, j), v) =>
        val tmp = v(i)
        v.updated(i, v(j)).updated(j, tmp)
    }
  }

Здесь вы просто выбираете все свои операции свопинга в Rng монадой, а затем сложите их, собрав их в качестве аккумулятора и меняя их по ходу.

Answer 3

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

import com.nicta.rng.Rng
import scalaz._
import Scalaz._

object FisherYatesShuffle {

  def randomJ(i: Int): Rng[Int] = Rng.chooseint(0,i)

  type Exchange = (Int,Int)

  def applyExchange[A](exchange: Exchange)(l: Vector[A]): Vector[A] = {
    val (i,j) = exchange
    val vi = l(i)
    l.updated(i,l(j)).updated(j,vi)
  }

  def stApplyExchange[A](exchange: Exchange): State[Vector[A], Unit] = State.modify(applyExchange(exchange))

  def shuffle[A](l: Vector[A]): Rng[Vector[A]] = {
    val rngExchanges: Rng[Vector[Exchange]] = (l.length - 1 to 1 by -1).toVector.traverseU { i =>
      for {
        j <- randomJ(i)
      } yield (i, j)
    }

    for {
      exchanges <- rngExchanges
    } yield exchanges.traverseU(stApplyExchange[A]).exec(l)
  }

}