Same input repeatedly tested during shrinking

[TysonMN]

While attempting to reproduce the behavior described in #223, I think I found some surprising behavior.

My investigative goal was to see what is the sequence of inputs generated when shrinking a simple generator. Here is the code I tried.

module Tests

open Xunit
open Xunit.Abstractions
open Hedgehog

type Tests (output: ITestOutputHelper) =
  
  [<Fact>]
  member _.test () =
    Property.check <| property {
      let! x = Range.constant 0 100 |> Gen.int
      x |> sprintf "%d" |> output.WriteLine
      Assert.Equal(0, x)
    }

The result of one execution of this test is...

Hedgehog.FailedException : *** Failed! Falsifiable (after 1 test and 7 shrinks):
1
Xunit.Sdk.EqualException: Assert.Equal() Failure
Expected: 0
Actual: 1

...and the values written to output are

66, 0, 33, 0, 17, 0, 9, 0, 5, 0, 3, 0, 2, 0, 1, 0

There are eight nonzero values, so they alone are the eight values involved in the seven shrinks.

Why is 0 tested so many times?

[TysonMN]

I think I better understand this behavior. From the failed value 66, the shrinking function returns

seq { 0; 33; 50; 58; 62; 64; 65 }

Then these values are tested in order (i.e. from left to right). The test first passes for 0 and then fails for 33. Then we repeat this process with 33 in the place of 66.

[TysonMN]

I think I better understand the semantics of the shrink tree now.

The root represents a value that causes the test to fail. The next value to test is its first child. If some child fails, then we recurse with the subtree rooted at that child. Whenever the value of a child causes the test to pass, then the value of the next child is tested. The shrinking process stops when the values of all children of some root value pass the test (which could be vacuously true when the root has no children).

And it isn't just 0 that is (or would be) repeated. Consider the shrink tree returned by this code.

let n = 4
let shrink = Shrink.towards 0
let tree = Tree.unfold id shrink n
tree |> Tree.map (sprintf "%A") |> Tree.render

4
├-0
├-2
| ├-0
| └-1
|   └-0
└-3
  ├-0
  └-2
    ├-0
    └-1
      └-0

Suppose the test passes for 0 to 2 and fails for 3 and 4. Then the sequence of tests would be

4, 0, 2, 3, 0, 2

which repeats both 0 and 2.

The "shrink tree" corresponding to the values considered in a binary search (which doesn't include any repeats) is

4
├-2
| └-1
|   └-0
└-3

[TysonMN]

For comparison, consider a recent improvement to Haskell Hedgehog, especially hedgehogqa/haskell-hedgehog#406 (comment).

In the example considered in that comment, there is an interval with values

"a", "b", "False", "True"

and these values are in order from "smallest" to "largest". The shrink tree starting at "True" is

"True"
 ├╼"a"
 ├╼"b"
 │  └╼"a"
 └╼"False"

Unlike the above shrink tree created by the F# code, this shrink tree "remembers" that "a" and "b" passed the test when the test fails for "False" (because "False" has no children).

[TysonMN]

When I created this issue, I knew that it was similar to the behavior improved by the Haskell PR, but I thought that maybe this issue was a slightly different issue that would be easier to fix. Now I am thinking that it is the same issue and I merely found a different way to demonstrate the inefficiency.

[moodmosaic]

Now I am thinking that it is the same issue and I merely found a different way to demonstrate the inefficiency.

That's right. I believe this behavior exists also in Haskell's Tree and it was 'patched' at the Gen level in hedgehogqa/haskell-hedgehog#406.

I haven't verified this yet, but the way I'd verify it is by runing GHCi and F# Interactive sessions side-by-side and comparing the results, having the GHCi one as reference (most of the times).

However, perhaps it'll be easier to quasiquote F# tests in Haskell and compare the two programmatically instead of relying on comparing them manually.

[TysonMN]

But how can it be the same issue? The fix in hedgehogqa/haskell-hedgehog#406 was only in the frequency function. The generator for which I created this issue is Gen.int, which is essentially Gen.integral. Furthermore, Gen.frequency depends on Gen.integral but not the other way around.

[moodmosaic]

Off the top of my head, I can't really tell about this particular one. I'd have to look closer. Your analysis is very helpful though.

[moodmosaic]

You mentioned in #224 (comment):

And it isn't just 0 that is (or would be) repeated. Consider the shrink tree returned by this code [..]

4
├-0
├-2
| ├-0
| └-1
|   └-0
└-3
  ├-0
  └-2
    ├-0
    └-1
      └-0

Do you consider that (rendered) tree correct? ⬆️ I'm pretty sure we do the exact same in Haskell if you execute this in GHCi (typing this on the top off my head)

import Hedgehog.Internal.Tree as Tree
import Hedgehog.Internal.Shrink as Shrink

tree = Tree.unfold (Shrink.towards 0) 4
Tree.render (fmap show tree)

---

Shouldn't the output be instead

4
├-2
| └-1
|   └-0
└-3

If yes, then fixing it at the tree/shrink level wouldn't require modifying each and every gen (as in hedgehogqa/haskell-hedgehog#406).

[TysonMN]

Do you consider that (rendered) tree correct? ⬆️ I'm pretty sure we do the exact same in Haskell if you execute this in GHCi (typing this on the top off my head)...

I am not certain that I know what you mean by "correct". One meaning is "the same as in Haskell Hedgehog". I expect you are right that the behavior of this code is the same for both the F# and Haskell versions of Hedgehog. (I would test it, but I don't know how to setup a Haskell environment. It is on my TODO list though.)

Another possible meaning is "as I expect". I expect that this tree corresponds to the values tested by binary search. In this sense, the tree is not correct.

Shouldn't the output be instead...

I think it should be that smaller tree instead.

If yes, then fixing it at the tree/shrink level wouldn't require modifying each and every gen (as in hedgehogqa/haskell-hedgehog#406).

Indeed. In fact, after achieving the behavior I expect for integral, I expect that I can simplify the implementation of frequency while maintaining / achieving the newly optimized behavior for frequency in Haskell Hedgehog.

[moodmosaic]

@ocharles, @HuwCampbell, it'd be nice to have your thoughts around this. ━ FYI, this is a continuation (and a generalization) of the discussion in hedgehogqa/haskell-hedgehog#406 (and hedgehogqa/haskell-hedgehog#118).

The idea here is that maybe we can work in the Tree instead of having to modify Gen.frequency and friends. So instead of

4
├-0
├-2
| ├-0
| └-1
|   └-0
└-3
  ├-0
  └-2
    ├-0
    └-1
      └-0

the output produced by

import Hedgehog.Internal.Tree as Tree
import Hedgehog.Internal.Shrink as Shrink

tree = Tree.unfold (Shrink.towards 0) 4
Tree.render (fmap show tree)

would be

4
├-2
| └-1
|   └-0
└-3

This was originally brought up by @TysonMN here in #224 (comment).

[TysonMN]

after achieving the behavior I expect for integral, I expect that I can simplify the implementation of frequency while maintaining / achieving the newly optimized behavior for frequency in Haskell Hedgehog.

The idea here is that maybe we can work in the Tree instead of having to modify Gen.frequency and friends.

I have not yet tried to achieve the behavior for frequency via this optimized implementation of integral that was achieved in PR hedgehogqa/haskell-hedgehog#406, but I expect that it would be similar to Gen.choice...

fsharp-hedgehog/src/Hedgehog/Gen.fs

Lines 258 to 259 in 333d331

	let! ix = integral <| Range.constant 0 (Array.length xs - 1)
	return! Array.item ix xs

...which uses an integral to select the index into an array of generators. The only difference is that the distribution of indices at the root of the shrink tree should be weighted.

[moodmosaic]

🏓 @ocharles
🏓 @HuwCampbell

[HuwCampbell]

In general we try to shrink smallest values first instead, as in complex structures this quickly removes irrelevant terms. So I don't think this would work very well

4
├-2
| └-1
|   └-0
└-3

Each sub-tree essentially repeats the same shrink strategy. This isn't too bad, as the number of duplicates is usually only the 0 term; and it means we'll always reach something small even after a few binds.

It might be possible for the trees to build something more like a binary search with smallest values tested first, but I can't off the top of my head I can't see how it would interact with bind and apply.

So the "ideal" tree may be more like this:

4
├-0
└-2
| └-1
└-3

But without an implementation and testing it with floating values and through a bind I can't say for sure.

[HuwCampbell]

Also, I have no idea how it would work for something like shrinking a list.

[TysonMN]

In general we try to shrink smallest values first instead, as in complex structures this quickly removes irrelevant terms. So I don't think this would work very well

I am not completely sure I understand what you mean. I will rephrase into my own words what I think you mean.

When shrinking, we try the smallest value first. This is very helpful when complex structures are involved because the smallest value is often causes the test to fail so this greatly decreases the time it takes to shrink.

In your proposed change, you no longer check the smallest value first, so I don't think your proposed change would work well.

Is that an accurate rephrasing of what you mean?

It might be possible for the trees to build something more like a binary search with smallest values tested first, but I can't off the top of my head I can't see how it would interact with bind and apply.

Might? I am not sure that we are on the same page. I have contributed PR #239 to fix this issue. My claim is that the code in that PR produces shrink trees that precisely correspond to the behavior of binary search.

My impression is that you would prefer to deviate from the exact behavior of binary search by testing the smallest value first. I want that behavior as well. However, I think the proper way to achieve that optimized behavior is to first create shrink trees that exactly match the behavior of binary search and then optimize them to test the smallest value first.

I think the applicative and monadic behaviors of Tree<'a> are the same. Am I right about that?

I think the applicative and monadic behaviors of Tree<'a> are independent of the change I am proposing in PR #239. The present issue is only about shrinking a single value. When there are multiple values involved, issue #223 is about the fact that the shrink process doesn't start by trying the minimal value for all of the multiple values involved. I also want to optimize that behavior, but I don't want to try and solve all of these problems at once.

[HuwCampbell]

Sorry I was a bit sloppy using might there.

Obviously for integers it is absolutely possible to build the tree I wrote above (although, as I'm sure you've noticed, not with the unfold and expand functions we have in the Haskell version.

Sorry I have never used f# at all nor looked at the implementation of fsharp-hedgehog; I can't comment on your PR. If you provide some examples over on that PR I would have more to say.

When shrinking, we try the smallest value first. This is very helpful when complex structures are involved because the smallest value is often causes the test to fail so this greatly decreases the time it takes to shrink.

This isn't quite what I meant.

When shrinking large product types, more often than not, only some of the elements are the cause of a failure. Shrinking to the smallest terms first means we quickly exclude irrelevant terms (ones which don't affect failure or success) from subsequent shrinking operations, and speeds up shrinking in general.

[TysonMN]

Obviously for integers it is absolutely possible to build the tree I wrote above [...]

I intend to optimize the shrink tree to start by testing the smallest value first. I think the proper way to obtain a shrink tree that both

1. does exactly what binary search would do
2. except that the smallest value is tested first

is to first do exactly what binary search would do and then modify that behavior to test the smallest value first.

I am using integers as an example. The code I wrote works for any integral type. The only non-integral type supported by fsharp-hedgehog seems to be double. I have not looked at how such shrink trees are created. Maybe they also have the same inefficiency. I don't know. I am trying to make progress by solving one small problem at a time instead of all the problems at the same time.

.[...] (although, as I'm sure you've noticed, not with the unfold and expand functions we have in the Haskell version.

Indeed. The way I see it, unfold and expand were a genius idea that allowed Hedgehog to turn a generic type from QuickCheck that is invariant in its type parameter into a generic type that is monadic in its type parameter. We don't have to stop there though. Now that we better understand this monadic type, we can move beyond its creation via unfold and expand and implement a more optimized version.

Shrinking to the smallest terms first means we quickly exclude irrelevant terms (ones which don't affect failure or success) from subsequent shrinking operations, and speeds up shrinking in general.

I don't know what you mean. Hedgehog sees the test as a black box. The only way it can exclude some term as irrelevant is by testing every possible input and in particular varying the term in question and observing that the outcome of the test is unchanged. However, that is not what Hedgehog does. Therefore, Hedgehog cannot exclude some term as irrelevant.

[HuwCampbell]

Sorry. I just mean this in (imagining haskell had records):

underTest :: { a: Int, b: Double, c: Int } -> Property
underTest = property $
  record <- forAll genRecord
  assert $ record.c < 15

Here the values of a and b in this product type are irrelevant to the test failure. Hedgehog will shrink these terms to 0 and 0.0 quickly, finding there is still a failure. It won't have any shrink more operations in its tree for them so will "concentrate" on finding the smallest c which yields an error.

[TysonMN]

Yep, that is the current behavior. And I want that behavior as well. I just think the proper way to obtain a shrink tree that both

1. does exactly what binary search would do
2. except that the smallest value is tested first

is to first do exactly what binary search would do and then modify that behavior to test the smallest value first.

[HuwCampbell]

Ok. I have written something in the Haskell version:

It gives this:

Gen.printTree $ Gen.int $ Range.constant 0 100
26
 ├╼ 0
 ├╼13
 │  ├╼ 7
 │  │  ├╼ 4
 │  │  │  ├╼ 2
 │  │  │  │  └╼ 1
 │  │  │  └╼ 3
 │  │  └╼ 6
 │  │     └╼ 5
 │  ├╼10
 │  │  ├╼ 8
 │  │  └╼ 9
 │  └╼12
 │     └╼11
 ├╼20
 │  ├╼16
 │  │  ├╼14
 │  │  └╼15
 │  ├╼18
 │  │  └╼17
 │  └╼19
 ├╼23
 │  └╼22
 │     └╼21
 └╼25
    └╼24

[HuwCampbell]

Here's the implementation if you're interested.

integral :: forall m a. (MonadGen m, Integral a) => Range a -> m a
integral range =
  let
    appendOrigin :: Tree.TreeT (MaybeT (GenBase m)) a -> Tree.TreeT (MaybeT (GenBase m)) a
    appendOrigin tree =
      Tree.TreeT $ do
        Tree.NodeT x xs <- Tree.runTreeT tree
        pure $
          Tree.NodeT x (xs <> [pure (Range.origin range)])

    binarySearchTree :: a -> Tree.TreeT (MaybeT (GenBase m)) a -> Tree.TreeT (MaybeT (GenBase m)) a
    binarySearchTree bottom tree =
      Tree.TreeT $ do
        Tree.NodeT x xs <- Tree.runTreeT tree
        let
          level =
            Shrink.towards bottom x
          zipped =
            zipWith (\b a -> binarySearchTree b (pure a)) (level) (drop 1 level)

        pure $
          Tree.NodeT x (xs <> zipped)

    withGenT' :: (GenT (GenBase m) a -> GenT (GenBase m) b) -> m a -> m b
    withGenT' = withGenT

  in
    withGenT' (mapGenT (binarySearchTree (Range.origin range) . appendOrigin)) (integral_ range)

[TysonMN]

Beautiful!

You just wrote that code, right? Do you plan to merge that code in?

[HuwCampbell]

Yes I did; and I will put a PR.

It does looks quite a lot better to the eye. I'm doing some comparisons with how it goes in the examples at the moment (seeing if it reduces the average number of shrinks and works well with nesting products and sums, I expect it will do well).

[HuwCampbell]

hedgehogqa/haskell-hedgehog#413

[TysonMN]

Excellent! :D

I will participate in that PR review. After it is complete, I will return to PR #239.