Clever Geek Handbook

How can I implement Shuffle Fisher-Yates in Scala without side effects?

I want to implement the Fischer-Yeiss algorithm (move an array in place) without side effects using STArray

for local mutation effects and a functional random number generator

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

to get the random integers needed by the algorithm.

I have a method def intInRange(max: Int): RNG[Int]

that I can use to generate a random Int

at [0, max).

From 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]

I suppose I need to stack State

with somehow ST

, but this is confusing me. Do i need [S]StateT[ST[S,?],Seed,A]

? Do I need to rewrite RNG

for use StateT

?

(Edit) I don't want to include IO

, and I don't want to substitute Vector

for STArray

, because the shuffle won't do in-place.

I know there is a Haskell implementation here , but I am not yet able to understand and port this to Scalaz. But maybe you can? :)

Thanks in advance.

+3


source to share


3 answers


Here's a more or less direct translation from the version of Haskell you linked to that uses mutable STArray

. Scalaz STArray

doesn't have an exact function equivalent listArray

, so I did it. Otherwise, it's a simple transliteration:

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
}


While the asymptotic behavior of using a volatile array may be good, note that the constant coefficients of the monad ST

in Scala are quite large. You might be better off doing this in a monolithic block using regular modified arrays. The shared function shuffle

stays clean because all of your mutable state is local.

+3


source


You have many options. One simple (but not very fundamental) one is to simply pick up operations in Rng

and ST

out IO

, and then work with them. Others would use both STRef[Long]

and STArray

in the same ST

. Others would use State[(Long, Vector[A]), ?]

.

You can use StateT[State[Long, ?], Vector[A], ?]

it too , but that would be pointless. You can probably use StateT

(for the RNG state) over ST

(for the array), but again, I really don't see the point.

This can be done fairly cleanly with no side effects with just Rng

. For example, using the NICTA 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)
    }
  }

Here, you simply select all your swaps in the monad Rng

and then add them together with your collection as an accumulator, swapping as you go.

+4


source


This is the same as Travis' solution, the difference is that he uses the state monad. I wanted to find a minimal set of imports, but I finally gave up:

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

}
+1


source






More articles:


All Articles