librarylibs/Random/src/Random.xtl

Random: randomness -- shuffles, deals, choices, uniform and normal samples, weighted picks. Import it with an alias of your choice: "r:" u_se< "Random". Put libs/Random/src on XETAL_PATH ("just path"); the reference is libs/Random/docs. Names with l: are exported; those under h: are private to this file.

Everything is built on the built-in r_oll!, so "xetal run --seed N" (or XETAL_SEED) makes a run repeatable. Every function has an effect and ends in !, as r_oll! does.

source

big : Int

value (private) · line 11

big ← 1000000000                             ⍝ the resolution of a draw

Used in: ʰk̲eys!, ˡu̲niform!

Shuffling

ʰk̲eys! : Int -> Int

function (private) · line 16

k random keys, 1..big.

ʰk̲eys! ← { k → r̲oll! k r̲eshape big }

Used in: ˡs̲huffle!, ˡu̲niform!

ˡs̲huffle! : a -> a

function · line 19

s_huffle! v: the items of v in a random order (sorting random keys).

ˡs̲huffle! ← { v → (g̲rade ʰk̲eys! t̲ally v) s̲elect v }

Used in: ˡd̲eal!

ˡd̲eal! : Int -> Int -> Int

function · line 22

k d_eal! n: k different numbers from 1..n, in random order (APL's deal).

ˡd̲eal! ← { k n →
  (k < 0) ∨ k > n ? @ p̲anic< "cannot deal {k} different numbers from 1 to {n}"
  k t̲ake ˡs̲huffle! r̲ange n
}

p̲anic< expands to

(⎕P̲ANIC ("cannot deal " c̲at (f̲ormat (k)) c̲at " different numbers from 1 to " c̲at (f̲ormat (n))))

ˡc̲hoice! : a -> a

function · line 28

c_hoice! v: one item of v, each as likely.

ˡc̲hoice! ← { v →
  0 = t̲ally v ? @ p̲anic< "there is nothing to choose from: the list is empty"
  (r̲oll! t̲ally v) s̲elect v
}

p̲anic< expands to

(⎕P̲ANIC ("there is nothing to choose from: the list is empty"))

ˡs̲ample! : Int -> a -> a

function · line 34

k s_ample! v: k items of v, each drawn afresh (with replacement).

ˡs̲ample! ← { k v →
  (0 = t̲ally v) ∧ k > 0 ? @ p̲anic< "there is nothing to sample from: the list is empty"
  (r̲oll! k r̲eshape t̲ally v) s̲elect v
}

p̲anic< expands to

(⎕P̲ANIC ("there is nothing to sample from: the list is empty"))

Used in: throws

Sampling distributions

ˡu̲niform! : Int -> Float

function · line 42

u_niform! n: n Floats, each as likely anywhere in [0, 1).

ˡu̲niform! ← { n → (f̲loat (ʰk̲eys! n) − 1) ÷ f̲loat big }

Used in: ˡn̲ormal!, ˡw̲eighted!, trees

ˡn̲ormal! : Int -> Float

function · line 46

n_ormal! n: n Floats from the standard normal distribution (mean 0, standard deviation 1), by the Box-Muller transform.

ˡn̲ormal! ← { n →
  a ← 1.0 − ˡu̲niform! n                      ⍝ in (0, 1], so l_og is finite
  b ← ˡu̲niform! n
  ((-2.0 × l̲og a) ^ 0.5) × c̲os 2.0 × b × p̲i @
}

ˡw̲eighted! : Num a => a -> Int -> Int

function · line 54

w w_eighted! k: k positions of w, each drawn with probability proportional to its weight (weights >= 0, not all 0).

ˡw̲eighted! ← { w k →
  c ← '+ s̲\ f̲loat w
  u ← (f̲irst -1 t̲ake c) × ˡu̲niform! k
  1 + '{ t̲ally w̲here c ≤ ⍵ } e̲ach u
}