# Examples/Random list

### From HaskellWiki

## 1 Create a random list

Generate a random list of numbers, without using the System.Random.randoms method:

import System.Random import Data.List main = do seed <- newStdGen let rs = randomlist 10 seed print rs randomlist :: Int -> StdGen -> [Int] randomlist n = take n . unfoldr (Just . random)

## 2 Delete an element at random

unpick and unpick' are by osfameron and are from http://osfameron.vox.com/library/post/more-random-fun.html (no explicit license) removeOne is by Chris Kuklewicz (BSD3 licence, 2007)

import System.Random import Control.Monad.State.Lazy import Debug.Trace -- for removeOne' demonstration

The unpick function and its helper unpick' are strict in the entire list being operated on (forcing it all into memory at once). And IO [a] cannot lazily return any initial values.

unpick :: [a] -> IO [a] unpick [] = undefined unpick [x] = return [] unpick (x:xs) = do zs <- unpick' [] [x] xs 2 return (reverse zs) unpick' :: (Num p, Random p) => [t] -> [t] -> [t] -> p -> IO [t] unpick' curr _ [] _ = return curr unpick' curr orig (next:rest) prob = do r <- getStdRandom (randomR (1,prob)) let curr' = if r == 1 then orig else (next:curr) unpick' curr' (next:orig) rest (prob+1)

(getStdRandom . removeOne) :: [a] -> IO [a].

removeOne

removeOne

removeOne

removeOne

Strict.Strict

tail

removeOne :: (RandomGen g) => [a] -> g -> ([a],g) removeOne [] = error "Cannot removeOne from empty list" removeOne whole@(_:xs) = runState (helper whole xs 0 1) where

rest</hsak> a lazy thunk. The

<hask>start

<hask>start

whole

oldIndex

whole

here

whole

index

^{th}element of whole as its head.

randomR

here

start

start

(index-oldIndex)

"start"

[]

0 <= oldIndex < index

helper start [] oldIndex index = return (tail start) helper start here@(_:ys) oldIndex index = do r <- State (randomR (0,index)) if r==0 then do rest <- helper here ys index $! succ index return (prependSome (index-oldIndex) start rest) else helper start ys oldIndex $! succ index

prependSome n xs ys == take n xs ++ ys

n >= length xs

prependSome :: Int -> [a] -> [a] -> [a] prependSome 0 _ rest = rest prependSome n (x:xs) rest = x : prependSome (pred n) xs rest prependSome _ [] _ = error "impossible error in removeOne.prependSome"

removeOne

removeOne' :: (Show a,RandomGen g) => [a] -> g -> ([a],g) removeOne' [] _ = error "Cannot removeOne from empty list" removeOne' whole@(x:xs) g = runState (helper whole xs 0 1) g where helper start [] oldIndex index = return (tail start) helper start here@(_:ys) oldIndex index = do r <- State (randomR (0,index)) if r==0 then do rest <- helper here ys index $! succ index let rest' = trace "." rest return (prependSome (index-oldIndex) start rest') else do let ys' = trace "_" ys helper start ys' oldIndex $! succ index

removeOne

removeOne

returning elements as soon as the removal decision has moved on to a later element (the "." is output instead of "_").

The element after the last "." is the one actually removed, defaulting to the first element.

Since the probability of "." decreases, the average length of the run of output produced byappendSome

*Main> getStdRandom (removeOne' [1..10]) [1. _ _ ,2,3,4. _ _ _ _ ,5,6,7,8,9. ] *Main> getStdRandom (removeOne' [1..10]) _ _ [1,2,3. _ _ _ _ _ _ ,5,6,7,8,9,10] *Main> getStdRandom (removeOne' [1..10]) _ _ _ _ _ _ _ _ _ [2,3,4,5,6,7,8,9,10] *Main> getStdRandom (removeOne' [1..10]) [1. _ _ _ _ _ _ _ _ ,3,4,5,6,7,8,9,10] *Main> getStdRandom (removeOne' [1..10]) [1. ,2. _ _ _ _ _ _ _ ,4,5,6,7,8,9,10] *Main> getStdRandom (removeOne' [1..10]) [1. _ _ _ _ ,2,3,4,5,6. _ _ ,7,8,9. ]

:m + Data.List Control.Monad

*Main Data.List Control.Monad> replicateM 1000 (getStdRandom (removeOne [1..4])) >>= return . map length . group . sort [241,255,239,265]

[250,250,250,250]