如何在Scala中实现Fisher-Yates shuffle而不产生副作用?

Question

我想通过使用STArray来实现无副作用的Fisher-Yates算法(就地数组洗牌)，用于局部突变效果，以及一个功能随机数生成器

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

生成算法所需的随机整数。

我有一个方法def intInRange(max: Int): RNG[Int]，我可以用它来产生一个随机的Int在[0,max)。

来自维基百科:

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 ?

(Edit)我不希望涉及IO，也不希望用Vector代替STArray，因为shuffle不会就地执行。

我知道这里有一个Haskell实现，但我目前无法理解并将其移植到Scalaz。但也许你可以?:)

Answer 1

你有很多选择。一个简单(但不是很有原则)的方法是将Rng和ST操作都提升到IO中，然后在那里一起使用它们。另一种方法是在同一个ST中同时使用STRef[Long]和STArray。另一种方法是使用State[(Long, Vector[A]), ?] .

您也可以使用StateT[State[Long, ?], Vector[A], ?]，但这将是毫无意义的。您可能会使用StateT(用于RNG状态)而不是ST(用于数组)，但是再次强调，我真的不明白这一点。

使用Rng可以非常干净地完成此操作而没有副作用。例如，使用NICTA的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 monad中的所有交换操作，然后将它们折叠起来，将您的集合作为累加器，然后进行交换。

Answer 2

这是您链接的使用可变STArray的Haskell版本的或多或少的直接翻译。Scalaz 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
}

尽管使用可变数组的渐近性可能是好的，但请注意Scala中ST单子的常数因子相当大。您最好在使用常规可变数组的整体块中执行此操作。整个shuffle函数保持纯粹，因为所有的可变状态都是local。

Answer 3

这与Travis的解决方案几乎相同，唯一的区别是它使用了State单子。我想找到一个最小的导入集合，但我最终放弃了:

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)
  }
}