Picks a random number from a stream with uniform probability. O(1) space.

reservoir.hs

import System.Random

f :: [a] -> IO a
f xs = f' xs [] 1 where
  f' :: [a] -> [a] -> Int -> IO a
  f' [] z _ = return $ head z
  f' (x:xs) z i = do r <- randomRIO (1,i)
                     if r == 1
                       then f' xs [x] (i + 1)
                       else f' xs z (i + 1)