29. Random values¶
This chapter is about the module random: samples, shuffles, choices,
random numbers and UUIDs. It covers the two forms each draw has, the seeded
one and the unseeded one, and the evaluation seed that makes a program's
random output repeatable.
The module¶
random is not in the prelude: a program binds its functions,
from random import *, or writes import random and calls
random.sample(…). Each draw
has two forms. With a seed argument it is pure: its result is a
function of the seed, its input and its call site, the same on every run.
Without one it is effectful and draws from the evaluation seed, fixed
once per evaluation.
The generator is ChaCha12. A seeded draw is predictable by design, so no draw
of random is fit for a key, a token or any other secret.
Samples, shuffles and choices¶
sample(n) is n elements drawn without replacement, in the order they have
in the input:
from random import *
range(1, 21) | sample(5, seed = 7)
[1, 5, 8, 11, 12]
shuffle is every element in a uniformly random order, and choice one
element drawn uniformly:
from random import *
titles = cards | filter(c => c.metadata.category == "book") | map(c => c.title)
{shuffled: titles | shuffle(seed = 7), picked: titles | choice(seed = 7)}
{picked: "The Common Reader", shuffled: ["Leaves of Grass", "Frankenstein", "The Common Reader", "A Room of One's Own", "The Hobbit", "Mrs Dalloway", "Dune"]}
choice is an Option: over an empty input it is none. sample(n) with
n at or above the input's size is the whole input, and a negative n is an
evaluation error:
from random import *
nothing = [1, 2, 3] | filter(n => n > 5)
[nothing | choice(seed = 1), [1, 2, 3] | choice(seed = 1)]
[none, 3]
A collection without an order, such as a Set, is sorted by its elements
before it is sampled, so the sample does not depend on how the set was built.
A seed¶
A seeded draw is a function of its call site, its position in the program text, as well as of its seed. Two calls with one seed at two places are two draws:
from random import *
deck = ["a", "b", "c", "d", "e"]
[deck | shuffle(seed = 1), deck | shuffle(seed = 1)]
[["b", "d", "c", "e", "a"], ["b", "c", "a", "e", "d"]]
One call site with one seed gives one result each time it is reached. A
seeded draw inside a map repeats; a seed that varies with the element
varies the draw:
from random import *
deck = ["a", "b", "c", "d"]
{same: range(0, 3) | map(_ => deck | shuffle(seed = 1)), varied: range(0, 3) | map(i => deck | shuffle(seed = i))}
{same: [["b", "a", "c", "d"], ["b", "a", "c", "d"], ["b", "a", "c", "d"]], varied: [["c", "b", "d", "a"], ["d", "a", "c", "b"], ["a", "c", "b", "d"]]}
Moving a seeded call to another place in the program text changes its result; running the same program again does not.
The evaluation seed¶
An unseeded draw reads the evaluation seed. --seed <int> fixes it; without
--seed, the seed comes from the host's entropy. Each unseeded call site
draws from a stream derived from the evaluation seed and its position in the
program, so two call sites draw independently, and a program run twice with
one --seed writes the same values:
from random import *
xs = range(1, 11)
{sample: xs | sample(3), shuffled: xs | shuffle, picked: xs | choice}
{picked: 5, sample: [4, 5, 7], shuffled: [6, 10, 7, 5, 8, 2, 3, 4, 9, 1]}
An evaluation that takes its seed from the host reports it at info, with
the --seed that repeats it:
$ hql --report-level info eval 'import random
range(1, 11) | shuffle | size'
10
execute info[effect]: the evaluation seed is -7270767200120302920; `--seed -7270767200120302920` repeats this evaluation
--> <expression>:1:1
|
1 | import random
| ^
Without --seed, a block's values differ from run to run, but what holds of
every draw holds of each: a sample of n has n elements, and a shuffle
holds every element once:
from random import *
[range(0, 1000) | sample(3) | size, (range(0, 29) | shuffle | sort) == range(0, 29)]
[3, true]
Numbers¶
random_int(low, high) is an Int drawn uniformly from low to high,
both included, and random_float() a Float from 0.0 included to 1.0
excluded. Both are effectful and have no seeded form, so --seed is what
makes them repeatable:
from random import *
{dice: range(0, 5) | map(_ => random_int(1, 6)), fraction: random_float()}
{dice: [1, 2, 3, 1, 6], fraction: 0.5633124818544215}
high below low is an evaluation error:
from random import *
random_int(6, 1)
execute failure[invalid-argument]: `random_int` needs `high` at or above `low`, and 1 is below 6
--> <expression>:2:1
|
2 | random_int(6, 1)
| ^^^^^^^^^^^^^^^^
UUIDs¶
A UUID is written as lowercase hyphenated text. uuid(name, namespace) is
the version 5 UUID of a name in a namespace: a function of the two, with no
draw. The namespace is a UUID's text, or one of the standard namespaces
"dns", "url", "oid" and "x500":
from random import *
uuid("www.example.com", "dns")
"2ed6657d-e927-568b-95e1-2665a8aea6a2"
uuid() is a version 7 UUID. Its first 48 bits are the evaluation instant's
Unix milliseconds and the next 42 a counter, so the UUIDs of one evaluation
are distinct and sort in the order they were drawn:
from random import *
ids = range(0, 20) | map(_ => uuid())
[ids == sort(ids), size(Set(ids)) == 20]
[true, true]
Its remaining bits come from the evaluation seed. --now fixes the
evaluation instant (the evaluation clock)
and --seed the seed, and the two together make uuid() repeatable:
from random import *
[uuid(), uuid()]
["01a16cd1-04c0-706c-9aa2-de28c20754f4", "01a16cd1-04c0-706c-9aa2-de2983927b4e"]
A stream¶
sample(n) also takes a stream, by reservoir sampling: the step holds n
elements, never the stream, and gives its sample when the stream ends. A
stream that does not end gives no sample. The stream form is effectful
only.
What is next¶
Chapter 30 is about the modules that turn values into bytes and back: digests and encodings.