Bug in `Shrink.list` skips singleton?

[njlr]

I was adding reports to some of the challenges in The Shrinking Challenge, namely Length List.

Hedgehog was not finding the optimal shrink, so I took a look at Shrink.list.

It appears to skip over the singleton case?

#r "nuget: Hedgehog, 2.0.3"

open Hedgehog

for xs in Shrink.list [1; 2; 3] do
  printfn "%A" xs

// []
// [2; 3]
// [1; 3]
// [1; 2]

[njlr]

Looks like my bug is a test case.

fsharp-hedgehog/tests/Hedgehog.Tests/ShrinkTests.fs

Lines 54 to 58 in 150b0cb

	testCase "list shrinks a list by edging towards the empty list - example 1" <| fun _ ->
	let actual =
	Shrink.list [1; 2; 3]
	|> Seq.toList
	actual =! [[]; [2; 3]; [1; 3]; [1; 2]]

This is working as intended?

[moodmosaic]

Thank you for reporting this! Yes, it's working as intended -- the Haskell Hedgehog source has the identical behavior and even documents it in the docstring:

-- | Shrink a list by edging towards the empty list.
--
-- >>> list [1,2,3]
-- [[],[2,3],[1,3],[1,2]]

The F# implementation is (mostly) a faithful port. The root cause is halves using integer division:

halves 3 = [3; 1]    -- 3 → 3/2=1         → 0 (stop). Skips 2.
halves 4 = [4; 2; 1] -- 4 → 4/2=2 → 2/2=1 → 0 (stop). No gap.
halves 5 = [5; 2; 1] -- 5 → 5/2=2 → 2/2=1 → 0 (stop). Skips 3, 4.
halves 7 = [7; 3; 1] --                               Skips 2, 4, 5, 6.

Any odd value floors down, so certain intermediate k values are never passed to removes.

[moodmosaic]

But yes, the design has this inherent gap for odd-length lists.

In the above example, for length 3, this means singletons are never directly produced -- they're only reachable by recursively shrinking one of the 2-element results (e.g. [2; 3] shrinks to []; [3]; [2]).

Whether this meaningfully hurts your Shrinking Challenge results depends on whether the greedy shrink walk settles on a 2-element list without exploring further into its children, or whether the property under test causes it to miss the singleton path entirely.

[moodmosaic]

If all the 2-element children pass, the shrinker never descends into their subtrees -- so singletons are unreachable, not just indirect.

---

A possible fix is ceiling division in list only (halves is also used by towards for numeric shrinking where floor is correct):

let list (xs : List<'a>) : seq<List<'a>> =
    let n = List.length xs
    Seq.unfold (fun k -> if k <= 0 then None else Some (k, (k + 1) / 2)) n
    |> Seq.collect (fun k -> removes k xs)

Gives [3; 2; 1] for length 3 instead of [3; 1]. Cost is one extra removes call per halving step.

Note that this would be a breaking change for recheck data (child indices shift), but recheck data is already version-fragile.

[moodmosaic]

I will label this as a bug.

There's a concrete scenario where the shrinker produces a provably non-minimal result -- not a matter of opinion or performance tradeoff. The algorithm claims to edge towards the empty list but has unreachable intermediate sizes due to the halves gap.