tree: list shrinking that drops elements anywhere (Shrink.list) #13

New issue

Closed

opened 2026-09-13 21:24:23 +09:00 by natsukium · 1 comment

natsukium commented

2026-09-13 21:24:23 +09:00

Owner

Missing

List shrinking that removes elements anywhere (Hedgehog Shrink.list: drop halves, quarters, ... then single elements), instead of only trailing ones.

Why

listOf = bind (int lenRange) (n: vectorOf n g) shrinks the length first, which can only drop a suffix, then shrinks elements in place. A counterexample [ 5 0 0 0 7 ] keeps its zeros because dropping them means shrinking the length and moving 7, which the tree cannot express. This limits the quality of every list-shaped counterexample, and after gen.attrsOf (#4) also of attrset counterexamples (individual keys cannot be dropped).

Suggested shape

tree.list / tree.interleave (Hedgehog Tree.interleave + Shrink.list): the shrinks of a list of trees are "remove a chunk" candidates followed by per-element shrinks.
listOf and vectorOf switch to it; record keeps sequence.
While in there: tree.sequence uses genList + elemAt, O(n^2) per level; measure before and after.

## Missing List shrinking that removes elements *anywhere* (Hedgehog `Shrink.list`: drop halves, quarters, ... then single elements), instead of only trailing ones. ## Why `listOf = bind (int lenRange) (n: vectorOf n g)` shrinks the length first, which can only drop a suffix, then shrinks elements in place. A counterexample `[ 5 0 0 0 7 ]` keeps its zeros because dropping them means shrinking the length *and* moving `7`, which the tree cannot express. This limits the quality of every list-shaped counterexample, and after `gen.attrsOf` (#4) also of attrset counterexamples (individual keys cannot be dropped). ## Suggested shape - `tree.list` / `tree.interleave` (Hedgehog `Tree.interleave` + `Shrink.list`): the shrinks of a list of trees are "remove a chunk" candidates followed by per-element shrinks. - `listOf` and `vectorOf` switch to it; `record` keeps `sequence`. - While in there: `tree.sequence` uses `genList` + `elemAt`, O(n^2) per level; measure before and after.

natsukium referenced this issue

2026-09-13 21:24:52 +09:00

gen.attrsOf: attrsets with generated keys #4

natsukium commented

2026-09-14 00:44:15 +09:00

Author

Owner

Implemented in 6496eac, pushed to main.

Implemented in 6496eac, pushed to main.

natsukium closed this issue

2026-09-14 00:44:15 +09:00