scalaz - 如何在 Scala 中实现 Fisher-Yates shuffle 且没有副作用？

Question

我想通过使用用于局部突变效应的 STArray 和函数随机数生成器来实现无副作用的 Fisher-Yates 算法(就地数组洗牌)

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

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

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

来自Wikipedia :

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 实现 here ，但我目前无法理解并将其移植到 Scalaz。但也许你可以？ :)

提前致谢。

Answer 1

你有很多选择。一个简单的(但不是很有原则的)就是同时举起 Rng和ST运营进入IO然后在那里与他们一起工作。另一种方法是同时使用 STRef[Long]和一个STArray同样ST 。另一种方法是使用 State[(Long, Vector[A]), ?] .

您还可以使用StateT[State[Long, ?], Vector[A], ?]但这毫无意义。您可能可以使用 StateT (对于 RNG 状态)超过 ST (对于数组)，但我还是没有真正明白这一点。

只需 Rng 就可以非常干净地完成此操作，没有副作用。 ， 尽管。例如，使用 NICTA's RNG library :

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，然后用你的集合作为累加器折叠它们，边走边交换。