Skip to content

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.