Gen

Gen module: Hedgehog-style property-test value generators with integrated shrinking.

Shrinking is NOT a separate step bolted onto generation. Each generator produces a rose tree (GenTree(a)): a value plus a lazy list of smaller candidate values. When a property fails, the runner walks the tree toward a minimal counterexample — no bespoke shrink function required.

Because shrinking is embedded in the tree, combinators like bind / map automatically propagate shrinking correctly through dependent generators.

Typical use (see Check.all in check.march):

Check.all(Gen.list(Gen.int(-100, 100)), fn xs ->
  List.reverse(List.reverse(xs)) == xs
)

All generators are pure: they consume a GenRng and a size hint, and return a shrink tree plus the advanced RNG.

Generators that draw random numbers (int, bool, list, ...) need the Random module, so their docs show plain code. constant and the combinators over it run without randomness, and the tree_* helpers are pure, so those carry REPL examples (any GenRng record works as the seed there; constant passes it through unchanged).

Types

typeThunkThunk(a) = Thunk(Bool -> a)#

typeGenTreeGenTree(a) = GenTree(a, Thunk(List(GenTree(a))))#

typeGenRngGenRng = { s0 : Int, s1 : Int, s2 : Int, s3 : Int }#

typeGeneratorGenerator(a) = Generator(GenRng -> Int -> (GenTree(a), GenRng))#

Functions

fnascii_charascii_char() : Generator(Int)#

Printable ASCII character code (an Int) in [32, 126]. Shrinks toward 'a' (97).

fnbindbind(g : Generator(a), f : a -> Generator(b)) : Generator(b)#

Monadic composition for dependent generators. Shrinking covers both the seed value and the function's result — when the seed shrinks, f is replayed with the same RNG so outputs remain deterministically linked.

Examples

march> let rng = { s0: 1, s1: 2, s2: 3, s3: 4 }
march> let g = Gen.bind(Gen.constant(3), fn n -> Gen.list_of_size(n, Gen.constant(0)))
march> let (t_bind, _) = Gen.run(g, rng, 0)
march> Gen.tree_root(t_bind)
[0, 0, 0]

fnboolbool() : Generator(Bool)#

Uniform Bool; shrinks True -> False (a property that holds for False is usually simpler to reason about than one that holds for True).

fnconstantconstant(x : a) : Generator(a)#

A generator that always produces the same value. Has no shrink candidates and leaves the RNG untouched.

Examples

march> let rng = { s0: 1, s1: 2, s2: 3, s3: 4 }
march> let (t_const, _) = Gen.run(Gen.constant("hi"), rng, 0)
march> Gen.tree_root(t_const)
"hi"

fnelementelement(xs : {List(a) | len(_) > 0}) : Generator(a)#

Pick a uniform element from a non-empty list. Shrinks toward the first element (which is assumed to be the "simplest" by user convention). The list must be non-empty (a refinement on the parameter; an empty list panics).

Gen.element([:red, :green, :blue])

fnfilterfilter(g : Generator(a), pred : a -> Bool) : Generator(a)#

Rejection sampling: re-run the generator until it produces a value satisfying pred, up to 100 attempts. Shrink candidates that fail the predicate are pruned.

Use sparingly — very selective predicates can hurt performance. Prefer bind + a targeted sub-generator when possible. Panics if 100 consecutive candidates are rejected.

Examples

march> let rng = { s0: 1, s1: 2, s2: 3, s3: 4 }
march> let (t_filt, _) = Gen.run(Gen.filter(Gen.constant(4), fn n -> n > 0), rng, 0)
march> Gen.tree_root(t_filt)
4

fnfloatfloat(lo : Float, hi : Float) : Generator(Float)#

Uniform float in [lo, hi); shrinks toward 0.0 when the range contains it, otherwise toward the bound nearest 0, by halving the distance to the target. Candidates stop once within about 2^-20 of the value, to avoid unbounded shrink chains on floats.

fnforceforce(th : Thunk(a)) : a#

Force a thunk. The Bool argument is a parser workaround and is ignored.

Examples

march> Gen.force(Gen.Thunk(fn _ -> 7))
7

fnfrequencyfrequency(pairs : {List((Int, Generator(a))) | len(_) > 0}) : Generator(a)#

Weighted choice among (weight, gen) pairs: gen is picked with probability proportional to weight. Weights must be non-negative and at least one must be positive. Like one_of, shrinking stays within the chosen generator.

Gen.frequency([(9, Gen.int(0, 10)), (1, Gen.constant(-1))])

fnintint(lo : Int, hi : Int) : Generator(Int)#

Uniform integer in [lo, hi] inclusive, shrinking toward 0 when the range contains 0, otherwise toward the bound nearest 0 (lo for an all-positive range, hi for an all-negative one).

Gen.int(-100, 100)   -- shrinks toward 0
Gen.int(10, 20)      -- shrinks toward 10

fnint_sizedint_sized() : Generator(Int)#

Uniform integer in [0, size], using the generator's size hint as the upper bound (a negative size is treated as 0). Shrinks toward 0.

fnint_tree_towardint_tree_toward(target : Int, n : Int) : GenTree(Int)#

Build a shrink tree for an integer, shrinking toward target. The candidates are target first, then values closing half the remaining distance to n each step (a binary search); each candidate shrinks recursively toward the same target. n == target is a leaf.

Examples

march> List.map(Gen.tree_children(Gen.int_tree_toward(5, 9)), fn c -> Gen.tree_root(c))
[5, 7, 8]
march> List.length(Gen.tree_children(Gen.int_tree_toward(3, 3)))
0

fnlistlist(g : Generator(a)) : Generator(List(a))#

Generator for a list. The length is uniform in [0, size], where size is the size hint passed by the runner (grows from 0 to ~100 across runs).

Shrinking reduces both length (dropping a prefix of n, n/2, n/4, ... elements) and element values, producing genuinely minimal counterexamples. Each element is generated with the same size hint.

Gen.list(Gen.int(-100, 100))

fnlist_of_sizelist_of_size(n : Int, g : Generator(a)) : Generator(List(a))#

Generator for a list of exactly n elements (none when n <= 0). The first level of shrink candidates keeps the length and shrinks one element; deeper candidates use list's shrinking and may be shorter.

Examples

march> let rng = { s0: 1, s1: 2, s2: 3, s3: 4 }
march> let (t_fixed, _) = Gen.run(Gen.list_of_size(3, Gen.constant(0)), rng, 0)
march> Gen.tree_root(t_fixed)
[0, 0, 0]

fnlowercase_charlowercase_char() : Generator(Int)#

Lowercase ASCII letter code (an Int in [97, 122]). Shrinks toward 'a'.

fnlowercase_stringlowercase_string() : Generator(String)#

Generator for a string of lowercase letters a-z; length uniform in [0, size], shrinking toward shorter strings of as.

fnmapmap(g : Generator(a), f : a -> b) : Generator(b)#

Transform a generator's output. Shrinking is inherited from the input: every shrink candidate is mapped through f too.

Examples

march> let rng = { s0: 1, s1: 2, s2: 3, s3: 4 }
march> let (t_map, _) = Gen.run(Gen.map(Gen.constant(3), fn n -> n * 2), rng, 0)
march> Gen.tree_root(t_map)
6

fnone_ofone_of(gens : {List(Generator(a)) | len(_) > 0}) : Generator(a)#

Uniform choice among a non-empty list of generators; the chosen generator's own shrinking applies (it does not shrink toward another alternative).

Gen.one_of([Gen.constant(0), Gen.int(1, 9)])

fnoptionoption(g : Generator(a)) : Generator(Option(a))#

Generator that produces None about 1/4 of the time and Some(x) from g the rest. Shrinks Some(x) toward None first, then shrinks x.

Gen.option(Gen.int(0, 10))

fnrunrun(g : Generator(a), rng : GenRng, size : Int) : (GenTree(a), GenRng)#

Run a generator with an RNG state and a size hint, returning the shrink tree and the advanced RNG. This is what Check.all calls once per run; call it directly to inspect what a generator produces.

Examples

march> let rng = { s0: 1, s1: 2, s2: 3, s3: 4 }
march> let (t_run, rng2) = Gen.run(Gen.constant(42), rng, 10)
march> Gen.tree_root(t_run)
42
march> let rng = { s0: 1, s1: 2, s2: 3, s3: 4 }
march> let (t_run, rng2) = Gen.run(Gen.constant(42), rng, 10)
march> rng2 == rng
true

fnsizedsized(f : Int -> Generator(a)) : Generator(a)#

Access the current size hint inside a generator. Use to build generators whose structure depends on the runner's size parameter (which grows from 0 to max_size across runs).

Example — lists that grow with size: let growing = Gen.sized(fn s -> Gen.list_of_size(s, Gen.int(0, 100)))

Example — nested structures bounded by size: let depth_bounded = Gen.sized(fn s -> if s < 2 do Gen.constant(Leaf) else Gen.map(Gen.int(0, 100), fn n -> Node(n)) end )

Examples

march> let rng = { s0: 1, s1: 2, s2: 3, s3: 4 }
march> let (t_sized, _) = Gen.run(Gen.sized(fn s -> Gen.constant(s * 2)), rng, 21)
march> Gen.tree_root(t_sized)
42

fnstringstring() : Generator(String)#

Generator for an ASCII string. Length uniform in [0, size]; characters drawn from printable ASCII (see ascii_char). Shrinks by reducing length and char values.

fnstring_ofstring_of(char_gen : Generator(Int)) : Generator(String)#

Generator for a string whose characters are drawn from char_gen. Use this to build domain-specific string generators. Length is uniform in [0, size]; each code is converted with char_from_int.

Example — hex strings: let hex_char = Gen.element([48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 97, 98, 99, 100, 101, 102]) let hex_string = Gen.string_of(hex_char)

Example — digit strings: let digit = Gen.int(48, 57) let digit_string = Gen.string_of(digit)

fntree_bindtree_bind(t : GenTree(a), f : a -> GenTree(b)) : GenTree(b)#

Monadic bind on trees. For each value in ta we produce a new tree via f; the resulting tree's children are the union of: (1) shrinks inherited from ta (each re-threaded through f) (2) shrinks of the f(root) sub-tree This is how integrated shrinking preserves relationships between dependent generators — shrinking the input automatically re-derives the output. f is applied to the root eagerly and to the children lazily.

Examples

march> let t = Gen.tree_bind(Gen.int_tree_toward(0, 2), fn n -> Gen.int_tree_toward(0, n + 1))
march> Gen.tree_root(t)
3
march> let t = Gen.tree_bind(Gen.int_tree_toward(0, 2), fn n -> Gen.int_tree_toward(0, n + 1))
march> List.map(Gen.tree_children(t), fn c -> Gen.tree_root(c))
[1, 2, 0, 1, 2]

fntree_childrentree_children(t : GenTree(a)) : List(GenTree(a))#

Force one level of shrink candidates, simplest first. A leaf (e.g. from tree_singleton) has none.

Examples

march> List.map(Gen.tree_children(Gen.int_tree_toward(0, 10)), fn c -> Gen.tree_root(c))
[0, 5, 7, 8, 9]
march> List.length(Gen.tree_children(Gen.tree_singleton("x")))
0

fntree_filtertree_filter(t : GenTree(a), pred : a -> Bool) : Option(GenTree(a))#

Filter a tree: keep only nodes whose root satisfies pred. A child that fails the predicate is dropped together with its whole subtree (its own children are not promoted). Returns None if the root itself fails the predicate.

Examples

march> let t = Gen.int_tree_toward(0, 6)
march> List.map(Gen.tree_children(t), fn c -> Gen.tree_root(c))
[0, 3, 4, 5]
march> let t = Gen.int_tree_toward(0, 6)
march> Option.map(Gen.tree_filter(t, fn n -> n > 2), fn f -> List.map(Gen.tree_children(f), fn c -> Gen.tree_root(c)))
Some([3, 4, 5])
march> let t = Gen.int_tree_toward(0, 6)
march> Option.is_none(Gen.tree_filter(t, fn n -> n > 9))
true

fntree_maptree_map(t : GenTree(a), f : a -> b) : GenTree(b)#

Map a pure function over every node in the tree. The shape of the tree (which shrinks are tried, in what order) is preserved; only the values change. Children are mapped lazily, when forced.

Examples

march> let t = Gen.tree_map(Gen.int_tree_toward(0, 4), fn n -> n * 10)
march> Gen.tree_root(t)
40
march> let t = Gen.tree_map(Gen.int_tree_toward(0, 4), fn n -> n * 10)
march> List.map(Gen.tree_children(t), fn c -> Gen.tree_root(c))
[0, 20, 30]

fntree_roottree_root(t : GenTree(a)) : a#

Extract the root value of a shrink tree (the generated value itself).

Examples

march> Gen.tree_root(Gen.int_tree_toward(0, 10))
10

fntree_singletontree_singleton(v : a) : GenTree(a)#

A tree with root v and no shrink candidates.

Examples

march> Gen.tree_root(Gen.tree_singleton("x"))
"x"

fntuple2tuple2(ga : Generator(a), gb : Generator(b)) : Generator((a, b))#

Generator for a 2-tuple, built with bind: shrinks the first component (re-running the second with the same RNG), then the second.

Examples

march> let rng = { s0: 1, s1: 2, s2: 3, s3: 4 }
march> let (t_pair, _) = Gen.run(Gen.tuple2(Gen.constant(1), Gen.constant("a")), rng, 0)
march> Gen.tree_root(t_pair)
(1, "a")

fntuple3tuple3(ga : Generator(a), gb : Generator(b), gc : Generator(c)) : Generator((a, b, c))#

Generator for a 3-tuple; shrinks like tuple2, component by component.

Examples

march> let rng = { s0: 1, s1: 2, s2: 3, s3: 4 }
march> let (t_trip, _) = Gen.run(Gen.tuple3(Gen.constant(1), Gen.constant("a"), Gen.constant(true)), rng, 0)
march> Gen.tree_root(t_trip)
(1, "a", true)