[Haskell-cafe] Bug in random shuffle algorithm

[Li-yao Xia]

Hello,

Thank you David for reporting this and thank you Viktor for the fix. I 
edited the wiki.

Li-yao

On 05/09/2017 01:46 AM, Viktor Dukhovni wrote:
>> On May 8, 2017, at 12:02 PM, David Turner <dct25-561bs at mythic-beasts.com> wrote:
>>
>> But this doesn't yield a uniformly-chosen random permutation of its input, because at the i'th step the first `i` elements are not fixed as they are in the other algorithms on that page.
> Channeling Samuel Dukhovni, who provided a patch for the same bug in
> older versions of Postfix a few years back, his suggested patch is:
>
>   shuffle :: RandomGen g => [a] -> Rand g [a]
>   shuffle xs = do
>       let l = length xs
> -     rands <- take l `fmap` getRandomRs (0, l-1)
> +     rands <- forM [0..(l-1)] (\i -> getRandomR (i, l-1))
>       let ar = runSTArray $ do
>           ar <- thawSTArray $ listArray (0, l-1) xs
>           forM_ (zip [0..(l-1)] rands) $ \(i, j) -> do
>               vi <- readSTArray ar i
>               vj <- readSTArray ar j
>               writeSTArray ar j vi
>               writeSTArray ar i vj
>           return ar
>       return (elems ar)
>
> Perhaps someone can forward this along to the package maintainer.
>
> Also as an optimization, the `rands` list should be made one element
> shorter, and likewise the `zip [0..(l-1)]` should become `zip [0..(l-2)]`.
> The reason is of course that by the time we only have one final element
> left there's nothing left to permute.
>