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

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 have

type RNG[A] = State[Long,A] // threads random seed
def intInRange(max: Int): RNG[Int] // returns a random `Int` in [0,max)

and from there, I'm trying to understand how to stack State with ST. Do I need a [S]StateT[ST[S,?],Long,A]? Do I have to rewrite RNG to use StateT as well?

For references, I've been looking at:

• FP in Scala
• eed3si9n
• scalaz.StateT
• scalaz.effect.ST

I know there is a Haskell implementation here, but I'm not currently capable of understanding and porting this to Scalaz. But maybe you can? :)

Thanks in advance.