[Haskell-cafe] Strange random choice algorithm

Sebastian Fischer sebf at informatik.uni-kiel.de
Sun Jan 31 03:52:15 EST 2010

On Jan 31, 2010, at 12:06 AM, Sebastian Fischer wrote:

>    pick xs = do n <- randomRIO (1,length xs)
>                 return (xs!!(n-1))
> would have been clearer.. It queries the random number generator  
> only once but walks through the list twice.

Walking through the list twice leads to linear memory requirements  
because the list cannot be garbage collected during the evaluation of  
length. If you intend to use this function with very long lists, the  
original algorithm is preferable. Here is a rewriting:

     import System.Random (randomRIO)
     import Control.Monad (foldM)

     pick (x:xs) = foldM swap x $ zip xs [2..]
      where swap y (z,n) = do m <- randomRIO (1::Integer,n)
                              if m==1 then return z else return y

This version of `pick` runs in constant space.


Underestimating the novelty of the future is a time-honored tradition.

More information about the Haskell-Cafe mailing list