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.)
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
