A method of choosing a line randomly from a file:

 Without reading the file more than once
 When substantial parts of the file cannot be held in memory
 Without knowing how many lines are in the file
Is to:

 keep the first line of the file as a possible choice, then
 Read the second line of the file if possible and make it the possible choice if a uniform random value between zero and one is less than 1/2.
 Read the third line of the file if possible and make it the possible choice if a uniform random value between zero and one is less than 1/3.
 ...
 Read the Nth line of the file if possible and make it the possible choice if a uniform random value between zero and one is less than 1/N
 Return the computed possible choice when no further lines exist in the file.


Task

 Create a function/method/routine called one_of_n that given n, the number of actual lines in a file, follows the algorithm above to return an integer - the line number of the line chosen from the file. 
The number returned can vary, randomly, in each run.
 Use one_of_n in a simulation to find what woud be the chosen line of a 10 line file simulated 1,000,000 times.
 Print and show how many times each of the 10 lines is chosen as a rough measure of how well the algorithm works.


Note: You may choose a smaller number of repetitions if necessary, but mention this up-front.

Note: This is a specific version of a Reservoir Sampling algorithm: https://en.wikipedia.org/wiki/Reservoir_sampling

import qualified Data.Map as M
import System.Random
import Data.List
import Control.Monad
import System.Environment
 
testFile = [1..10]
 
selItem g xs = foldl' f (head xs, 1, 2, g) $ tail xs
    where f :: RandomGen a => (b, Int, Int, a) -> b -> (b, Int, Int, a)
          f (c, cn, n, gen) l | v == 1    = (l, n, n+1, ngen)
                              | otherwise = (c, cn, n+1, ngen)
            where (v, ngen) = randomR (1, n) gen
 
oneOfN a = do
            g <- newStdGen
            let (r, _, _, _) = selItem g a
            return r
 
test = do
        x <- replicateM 1000000 (oneOfN testFile)
        let f m l = M.insertWith (+) l 1 m
        let results = foldl' f M.empty x
        forM_ (M.toList results) $ \(x, y) -> putStrLn $ "Line number " ++ show x ++ 
								 " had count :" ++ show y
 
main = do
        a <- getArgs
        g <- newStdGen
        if null a then test
                  else putStrLn.(\(l, n, _, _) -> "Line " ++
                               show n ++ ": " ++ l)
                       .selItem g.lines =<< (readFile $ head a)