<div class="gmail_quote"><br><br>I&#39;ve abeen recommended on good authority(my son, a Cambridge Pure maths graduate, and Perl/Haskell expert) , and backed by a Google search that Fisher-Yates shuffle is the  one to use, as it produces total unbiased results with every combination equally possible. <div>

As with most things with computers,don&#39;t reinvent the eheel, it&#39;s almost certainly been done before by someone brighter that you, Fisher,Yates. &amp; Knuth!</div><div>--</div><div>Andrew Smith B.Sc(Hons),MBA</div>

<div>Edinburgh,Scotland<div><div></div><div class="h5"><br><br><div class="gmail_quote">On 27 August 2010 21:02, Gaius Hammond <span dir="ltr">&lt;<a href="mailto:gaius@gaius.org.uk" target="_blank">gaius@gaius.org.uk</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi all,<br>
<br>
<br>
<br>
I am trying to randomly reorder a list (e.g. shuffle a deck of cards) . My initial approach is to treat it as an array, generate a list of unique random numbers between 0 and n - 1, then use those numbers as new indexes. I am using a function to generate random numbers in the State monad as follows:<br>


<br>
<br>
<br>
randInt∷  Int →  State StdGen Int<br>
randInt x = do g ←  get<br>
               (v,g&#39;) ←  return $ randomR (0, x) g<br>
               put g&#39;<br>
               return v<br>
<br>
<br>
<br>
This is pretty much straight from the documentation. My function for the new indexes is:<br>
<br>
<br>
<br>
-- return a list of numbers 0 to x-1 in random order                                       randIndex∷ Int → StdGen → ([Int], StdGen)<br>
randIndex x = runState $ do<br>
    let randIndex&#39; acc r<br>
            | (length acc ≡ x) = acc<br>
            | (r `elem` acc) ∨ (r ≡  (−1)) = do<br>
                r&#39; ← randInt (x − 1)<br>
                randIndex&#39; acc r&#39;<br>
            | otherwise = do<br>
                r&#39; ← randInt (x − 1)<br>
                randIndex&#39; r:acc r&#39;<br>
        in<br>
        randIndex&#39; [] (−1)<br>
<br>
<br>
<br>
This fails to compile on<br>
<br>
<br>
<br>
<br>
   Couldn&#39;t match expected type `[a]&#39;<br>
           against inferred type `State StdGen b&#39;<br>
    In a stmt of a &#39;do&#39; expression: r&#39; &lt;- randInt (x - 1)<br>
    In the expression:<br>
        do { r&#39; &lt;- randInt (x - 1);<br>
             randIndex&#39; acc r&#39; }<br>
<br>
<br>
<br>
<br>
I can see what&#39;s happening here - it&#39;s treating randIndex&#39; as the second argument to randInt instead of invisibly putting the State in there. Or am I going about this completely the wrong way?<br>
<br>
<br>
Thanks,<br>
<br>
<br>
<br>
G<br>
<br>
<br>
<br>
<br>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a><br>
</blockquote></div><br></div></div></div>
</div><br>