[Haskell-cafe] Strange random choice algorithm

[Sebastian Fischer]

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.

Sebastian


-- 
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)