3

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？

（编辑）我不想参与IO，也不想替代Vector，STArray因为洗牌不会就地执行。

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

提前致谢。

4

3 回答 3

4

你有很多选择。一种简单（但不是很有原则）的方法就是将RngandST操作都提升到IO其中，然后在那里与它们一起工作。另一种方法是同时使用 an和STRef[Long]an 。另一种方法是使用.STArraySTState[(Long, Vector[A]), ?]

您也可以使用 a StateT[State[Long, ?], Vector[A], ?]，但这毫无意义。您可能可以 StateT在（用于数组）上使用（用于 RNG 状态）ST，但同样，我真的不明白这一点。

不过，使用 just 可以非常干净地做到这一点而没有副作用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)
    }
  }

在这里，您只需选择Rngmonad 中的所有交换操作，然后将它们折叠起来，并将您的集合作为累加器，随时交换。

于 2015-05-25T14:41:41.913 回答
3

这是您链接的使用 mutable的Haskell 版本的或多或少的直接翻译STArray。ScalazSTArray没有与该功能完全等效的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
}

尽管使用可变数组的渐近性可能很好，但请注意STScala 中 monad 的常数因子非常大。使用常规可变数组在一个整体块中执行此操作可能会更好。整个shuffle函数保持纯净，因为您所有的可变状态都是local。

于 2015-05-26T03:32:55.347 回答
1

这与 Travis 解决方案几乎相同，唯一的区别是它使用了 State monad。我想找到一个最小的进口集，但我最终放弃了：

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

}
于 2015-05-26T01:46:17.407 回答