[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.
Sebastian
--
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)
More information about the Haskell-Cafe
mailing list