module Random
( Generator, Seed
, int, float
, list, pair
, minInt, maxInt
, generate, initialSeed
, customGenerator
)
where
{-| This library helps you generate pseudo-random values.
The general pattern is to define a `Generator` which can produce certain kinds
of random values. You actually produce random values by feeding a fresh `Seed`
to your `Generator`.
Since you need a fresh `Seed` to produce more random values, you should
probably store a `Seed` in your application's state. This will allow you to
keep updating it as you generate random values and fresh seeds.
The following example models a bunch of bad guys that randomly appear. The
`possiblyAddBadGuy` function uses the random seed to see if we should add a bad
guy, and if so, it places a bad guy at a randomly generated point.
type alias Model =
{ badGuys : List (Float,Float)
, seed : Seed
}
possiblyAddBadGuy : Model -> Model
possiblyAddBadGuy model =
let (addProbability, seed') =
generate (float 0 1) model.seed
in
if addProbability < 0.9
then
{ model |
seed <- seed'
}
else
let (position, seed'') =
generate (pair (float 0 100) (float 0 100)) seed'
in
{ model |
badGuys <- position :: model.badGuys
seed <- seed''
}
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
# Custom Generators
@docs customGenerator
-}
import Basics exposing (..)
import List exposing ((::))
{-| Create a generator that produces 32-bit integers in a given range. This
function *can* 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 =
Generator <| \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 32-bit ints. -}
maxInt : Int
maxInt = 2147483647
{-| The minimum value for randomly generated 32-bit ints. -}
minInt : Int
minInt = -2147483648
{-| Create a generator that produces floats in a given range.
probability : Generator Float
probability =
float 0 1
-- generate probability seed0 ==> (0.51, seed1)
-- generate probability seed1 ==> (0.04, seed2)
-}
float : Float -> Float -> Generator Float
float a b =
Generator <| \seed ->
let (lo, hi) = if a < b then (a,b) else (b,a)
(number, seed') =
generate (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 (Generator genLeft) (Generator genRight) =
Generator <| \seed ->
let (left , seed' ) = genLeft seed
(right, seed'') = genRight seed'
in
((left,right), seed'')
{-| Create a list of random values.
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 (Generator generate) =
Generator <| \seed ->
listHelp [] n generate seed
listHelp : List a -> Int -> (Seed -> (a,Seed)) -> Seed -> (List a, Seed)
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'
{-| Create a custom generator. You provide a function that takes a seed, and
returns a random value and a new seed. You can use this to create custom
generators not covered by the basic functions in this library.
pairOf : Generator a -> Generator (a,a)
pairOf generator =
customGenerator <| \seed ->
let (left , seed' ) = generate generator seed
(right, seed'') = generate generator seed'
in
((left,right), seed'')
-}
customGenerator : (Seed -> (a, Seed)) -> Generator a
customGenerator generate =
Generator generate
{-| 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.
-}
type Generator a =
Generator (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 31415
-- generate (int 0 100) seed0 ==> (42, seed1)
-- generate (int 0 100) seed1 ==> (31, seed2)
-- generate (int 0 100) seed2 ==> (99, 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 0 100) seed0 ==> (42, seed1)
-- generate (int 0 100) seed0 ==> (42, seed1)
-- generate (int 0 100) seed0 ==> (42, seed1)
-}
generate : Generator a -> Seed -> (a, Seed)
generate (Generator 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)