StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Below is one way of implementing an in-place Fisher-Yates (I think that is called a Durstenfeld or Knuth Shuffle). Notice that <code>runST</code> is never called, but <code>runSTArray</code> instead, and it is only called once.</p> <pre><code>import Data.Array import Data.Array.ST import Control.Monad.ST import Control.Monad import System.Random fisherYates :: (RandomGen g,Ix ix, Random ix) => g -> Array ix e -> Array ix e fisherYates gen a' = runSTArray $ do a <- thaw a' (bot,top) <- getBounds a foldM (\g i -> do ai <- readArray a i let (j,g') = randomR (bot,i) g aj <- readArray a j writeArray a i aj writeArray a j ai return g') gen (range (bot,top)) return a </code></pre> <p>Note that although the algorithm is performed in-place, the function first copies the array given in the input (a result of using the function <code>thaw</code>) before performing the algorithm on the copy. In order to avoid copying the array you have at least two options:</p> <ol> <li><p>Use <code>unsafeThaw</code>, which is (as the name suggests) unsafe and can only be used if you<br> are sure that the input array will never be used again. This is not trivial to guarantee because of lazy evaluation.</p></li> <li><p>Let <code>fisherYates</code> have the type <code>(RandomGen g,Ix ix, Random ix) => g -> STArray s ix e -> ST s (STArray s ix e)</code> and perform the whole operation that requires an in-place fisher-yates algorithm inside the <code>ST</code> monad and only give the final answer with <code>runST</code>.</p></li> </ol>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload