tree

A lazy rose tree: a value paired with an on-demand stream of “smaller” alternatives. Generators in metamon return Tree(a) instead of bare values so shrinking is always available without separate plumbing.

The lazy stream type Shrinks(a) is defined locally instead of using an external lazy-list library, keeping metamon’s runtime dependencies limited to gleam_stdlib.

Types

ShrinkStep

</>

One step in a Shrinks(a) stream.

pub type ShrinkStep(a) {
  Done
  More(head: a, tail: Shrinks(a))
}

Constructors

```
Done
```
```
More(head: a, tail: Shrinks(a))
```

Shrinks

opaque </>

A lazy stream of shrink alternatives.

Each element is computed on demand by forcing step; once a Done step is observed the stream is exhausted. Shrinks(a) is functorial (map_shrinks), filterable (filter_shrinks), and concatenable (append_shrinks).

pub opaque type Shrinks(a)

Tree

</>

A value and its lazy shrink alternatives.

Each Tree(a) represents a single generated value (value) and a stream of smaller candidate trees (shrinks). The runner walks shrinks only when a property has failed.

pub type Tree(a) {
  Tree(value: a, shrinks: Shrinks(Tree(a)))
}

Constructors

Tree(value: a, shrinks: Shrinks(Tree(a)))

Values

append_shrinks

</>

pub fn append_shrinks(
  left: Shrinks(a),
  right: Shrinks(a),
) -> Shrinks(a)

Concatenate two Shrinks(a) streams. The right side is only consulted once the left is exhausted.

bind

</>

pub fn bind(tree: Tree(a), k: fn(a) -> Tree(b)) -> Tree(b)

Monadic bind. Each value’s continuation produces its own tree, and the returned tree shrinks both the outer (via the original shrinks) and the inner (via the continuation tree’s shrinks). Outer shrinks come first to prefer simplifying the seed-driven structure before rerunning the continuation.

filter

</>

pub fn filter(tree: Tree(a), predicate: fn(a) -> Bool) -> Tree(a)

Drop tree nodes that fail predicate. The root is assumed to satisfy the predicate (callers must ensure this; otherwise the result has no meaningful “current value”).

filter_shrinks

</>

pub fn filter_shrinks(
  stream: Shrinks(a),
  predicate: fn(a) -> Bool,
) -> Shrinks(a)

Lazily drop elements that fail predicate.

from_list

</>

pub fn from_list(value: a, shrinks: List(Tree(a))) -> Tree(a)

Build a tree from a value and a pre-computed list of sub-trees.

map

</>

pub fn map(tree: Tree(a), f: fn(a) -> b) -> Tree(b)

Map a function over every value in the tree, preserving the shrink structure.

map_shrinks

</>

pub fn map_shrinks(
  stream: Shrinks(a),
  f: fn(a) -> b,
) -> Shrinks(b)

Map a function over every element of a Shrinks(a) lazily.

no_shrinks

</>

pub fn no_shrinks() -> Shrinks(a)

An empty shrink stream.

outline

</>

pub fn outline(
  tree: Tree(a),
  depth: Int,
  breadth: Int,
) -> List(a)

Force the tree into a list of values up to depth levels deep, taking at most breadth shrinks per level. Used for inspection in tests.

shrinks_find

</>

pub fn shrinks_find(
  stream: Shrinks(a),
  predicate: fn(a) -> Bool,
) -> Result(a, Nil)

Find the first element satisfying predicate, or Error(Nil) if no such element exists in the (finite) stream.

shrinks_from_list

</>

pub fn shrinks_from_list(items: List(a)) -> Shrinks(a)

Build a Shrinks(a) from a list. Useful when the shrink alternatives are statically known (e.g. integer halving).

shrinks_take

</>

pub fn shrinks_take(stream: Shrinks(a), n: Int) -> List(a)

Force the first n elements of a stream into a list.

shrinks_to_list

</>

pub fn shrinks_to_list(stream: Shrinks(a)) -> List(a)

Force the entire stream into a list. Use only on streams known to be finite — generator shrink streams generally are, but be careful with infinite expansions.

singleton

</>

pub fn singleton(value: a) -> Tree(a)

A leaf tree with no shrink alternatives.

unfold

</>

pub fn unfold(value: a, expand: fn(a) -> List(a)) -> Tree(a)

Build a tree from a value and an expand function that produces direct child values. Each child is recursively expanded with the same function.

zip

</>

pub fn zip(left: Tree(a), right: Tree(b)) -> Tree(#(a, b))

Combine two trees pairwise. Used to give independent generators a clean product shrink: shrink the left first, then the right. This preserves the “shrink one component while holding the other” property that makes counter-examples easier to read.