module Random
( Generator, Seed
, int, float
, list, pair
, minInt, maxInt
, generate, initialSeed
)
where
{-| This library helps you generate pseudo-random values. The best way to use
it in your programs probably involves carrying a `Seed` in your application's
state.
Details: This is an implemenation of the Portable Combined Generator of
L'Ecuyer for 32-bit computers. It is almost a direct translation from the
[System.Random](http://hackage.haskell.org/package/random-1.0.1.1/docs/System-Random.html)
module. It has a period of roughly 2.30584e18.
# Generators
@docs int, float, pair, list
# Running a Generator
@docs generate, initialSeed
# Constants
@docs maxInt, minInt
# Creating Custom Generators
@docs Generator
-}
import Basics (..)
import List
import List ((::))
{-| Generate a 32-bit integer in a given range. This function will continue to
produce values outside of the range [minInt, maxInt] but sufficient
randomness is not guaranteed.
int 0 10 -- an integer between zero and ten
int -5 5 -- an integer between -5 and 5
int minInt maxInt -- an integer in the widest range feasible
-}
int : Int -> Int -> Generator Int
int a b seed =
let (lo,hi) = if a < b then (a,b) else (b,a)
k = hi - lo + 1
-- 2^31 - 87
base = 2147483561
n = iLogBase base k
f n acc state =
case n of
0 -> (acc, state)
_ -> let (x, state') = seed.next state
in f (n - 1) (x + acc * base) state'
(v, state') = f n 1 seed.state
in
(lo + v % k, { seed | state <- state' })
iLogBase : Int -> Int -> Int
iLogBase b i =
if i < b then 1 else 1 + iLogBase b (i // b)
{-| The maximum value for randomly generated for 32-bit ints. -}
maxInt : Int
maxInt = 2147483647
{-| The minimum value for randomly generated for 32-bit ints. -}
minInt : Int
minInt = -2147483648
{-| Generate a float in a given range.
-}
float : Float -> Float -> Generator Float
float a b seed =
let (lo, hi) = if a < b then (a,b) else (b,a)
(number, seed') =
int minInt maxInt seed
negativeOneToOne =
toFloat number / toFloat (maxInt - minInt)
scaled = (lo+hi)/2 + ((hi-lo) * negativeOneToOne)
in
(scaled, seed')
-- DATA STRUCTURES
{-| Create a pair of random values. A common use of this might be to generate
a point in a certain 2D space. Imagine we have a collage that is 400 pixels
wide and 200 pixels tall.
randomPoint : Generator (Int,Int)
randomPoint =
pair (int -200 200) (int -100 100)
-}
pair : Generator a -> Generator b -> Generator (a,b)
pair genLeft genRight seed =
let (left , seed' ) = genLeft seed
(right, seed'') = genRight seed'
in
((left,right), seed'')
{-| Create a list of random values using a generator function.
floatList : Generator (List Float)
floatList = list 10 (float 0 1)
intList : Generator (List Int)
intList = list 5 (int 0 100)
intPairs : Generator (List (Int, Int))
intPairs =
list 10 (pair int int)
-}
list : Int -> Generator a -> Generator (List a)
list n gen =
listHelp [] n gen
listHelp : List a -> Int -> Generator a -> Generator (List a)
listHelp list n generate seed =
if n < 1
then (List.reverse list, seed)
else
let (value, seed') = generate seed
in listHelp (value :: list) (n-1) generate seed'
{-| A `Generator` is a function that takes a seed, and then returns a random
value and a new seed. The new seed is used to generate new random values. You
can use this to define Generators of your own. For example, here is how
`pair` is implemented.
pair : Generator a -> Generator b -> Generator (a,b)
pair genLeft genRight seed =
let (left , seed' ) = genLeft seed
(right, seed'') = genRight seed'
in
((left,right), seed'')
-}
type alias Generator a =
Seed -> (a, Seed)
type State = State Int Int
type alias Seed =
{ state : State
, next : State -> (Int, State)
, split : State -> (State, State)
, range : State -> (Int,Int)
}
{-| Run a random value generator with a given seed. It will give you back a
random value and a new seed.
seed0 = initialSeed 42
-- generate int seed0 ==> (4123, seed1)
-- generate int seed1 ==> (-123, seed2)
-- generate int seed2 ==> (1021, seed3)
Notice that we use different seeds on each line. This is important! If you use
the same seed, you get the same results.
-- generate int seed0 ==> (4123, seed1)
-- generate int seed0 ==> (4123, seed1)
-- generate int seed0 ==> (4123, seed1)
-}
generate : Generator a -> Seed -> (a, Seed)
generate generator seed =
generator seed
{-| Create a “seed” of randomness which makes it possible to
generate random values. If you use the same seed many times, it will result
in the same thing every time! A good way to get an unexpected seed is to use
the current time.
-}
initialSeed : Int -> Seed
initialSeed n =
Seed (initState n) next split range
{-| Produce the initial generator state. Distinct arguments should be likely
to produce distinct generator states.
-}
initState : Int -> State
initState s' =
let s = max s' -s'
q = s // (magicNum6-1)
s1 = s % (magicNum6-1)
s2 = q % (magicNum7-1)
in
State (s1+1) (s2+1)
magicNum0 = 40014
magicNum1 = 53668
magicNum2 = 12211
magicNum3 = 52774
magicNum4 = 40692
magicNum5 = 3791
magicNum6 = 2147483563
magicNum7 = 2137383399
magicNum8 = 2147483562
next : State -> (Int, State)
next (State s1 s2) =
-- Div always rounds down and so random numbers are biased
-- ideally we would use division that rounds towards zero so
-- that in the negative case it rounds up and in the positive case
-- it rounds down. Thus half the time it rounds up and half the time it
-- rounds down
let k = s1 // magicNum1
s1' = magicNum0 * (s1 - k * magicNum1) - k * magicNum2
s1'' = if s1' < 0 then s1' + magicNum6 else s1'
k' = s2 // magicNum3
s2' = magicNum4 * (s2 - k' * magicNum3) - k' * magicNum5
s2'' = if s2' < 0 then s2' + magicNum7 else s2'
z = s1'' - s2''
z' = if z < 1 then z + magicNum8 else z
in
(z', State s1'' s2'')
split : State -> (State, State)
split (State s1 s2 as std) =
let new_s1 = if s1 == magicNum6-1 then 1 else s1 + 1
new_s2 = if s2 == 1 then magicNum7-1 else s2 - 1
(State t1 t2) = snd (next std)
in
(State new_s1 t2, State t1 new_s2)
range : State -> (Int,Int)
range _ =
(0, magicNum8)