Gen.filter scans entire shrink trees

[ChickenProp]

Consider the generator:

testGen :: Gen (Bool, Int)
testGen = (,) <$> b <*> i
 where
  node val sub = TreeT $ MaybeT $ Identity $ Just $ NodeT val sub
  b = GenT $ \_ _ -> node True [node False []]
  i = GenT $ \_ _ ->
    node 8
      [ node 0 []
      , node 4
          [ node 2 [ node 1 [] ]
          , node 3 [] ]
      , node 6 [ node 5 [] ]
      , node 7 [] ]

It has shrink tree

Just (True,8)
|- Just (False,8)
| |- Just (False,0)
| |- Just (False,4)
| | |- Just (False,2)
| | | |- Just (False,1)
| | |- Just (False,3)
| |- Just (False,6)
| | |- Just (False,5)
| |- Just (False,7)
|- Just (True,0)
| |- Just (False,0)
|- Just (True,4)
| |- Just (False,4)
| | |- Just (False,2)
| | | |- Just (False,1)
| | |- Just (False,3)
| |- Just (True,2)
| | |- Just (False,2)
| | | |- Just (False,1)
| | |- Just (True,1)
| | | |- Just (False,1)
| |- Just (True,3)
| | |- Just (False,3)
|- Just (True,6)
| |- Just (False,6)
| | |- Just (False,5)
| |- Just (True,5)
| | |- Just (False,5)
|- Just (True,7)
| |- Just (False,7)

Suppose we apply filter fst to it. It now has shrink tree

Just (True,8)
|- Just (True,0)
|- Just (True,4)
| |- Just (True,2)
| | |- Just (True,1)
| |- Just (True,3)
|- Just (True,6)
| |- Just (True,5)
|- Just (True,7)

as expected. But it runs the predicate on all of (False, 8), (False, 0), (False, 4), ... before running it on (True, 0). And after (True, 4) it tests all of (False, 4), (False, 2), (False, 1) and (False, 3) before (True, 2).

That is, if a value doesn't match the predicate, it goes on to try every possible shrink of that value.

One could argue that this is desired behavior. But it's quite capable of making shrinking spin with no apparent progress, when applied to something with a large shrink tree (e.g. Gen.text someRange unicode) where no amount of shrinking will ever make it pass the filter. I now think this is responsible for #452, and I won't be shocked if #426 as well.

IMO it should be considered undesirable by default and changed. If someone wants this behavior, there can be another function (filterCarefully?) that supplies it. But leaving the existing behavior as-is and supplying a new function (filterAggressively?) also seems like a fine option.

In any case, I think the fix is easy enough. Gen.mapMaybe simply needs to refer to Tree.mapMaybeT instead of Tree.mapMaybeMaybeT. mapMaybeT has the behavior "if a node fails the predicate, remove it entirely" while mapMaybeMaybeT has the behavior "if a node fails the predicate, replace it with its descendants that do". (Except that if the root of a tree fails the predicate, it does get removed entirely, which makes filter's behavior even more surprising which doesn't affect filter because that ever applies it to a passing root.)

If filter does keep its current behavior, it should be clarified in the docs. Right now it says it's roughly

filter p gen = mfilter p gen <|> filter p gen

except that it avoids looping forever. But that definition wouldn't behave like this; mfilter also removes nodes entirely. So if this isn't considered a bug in implementation, it's certainly a bug in documentation.

(While we're at it, I think it's also worth noting that filter grows the generator while it loops.)

By default I intend to fix this in my own fork tomorrow, by changing the behavior and not creating a replacement. If a maintainer wants a PR to this repo as well, I'm happy to supply it if you tell me which fix you want. (i.e. change behavior of filter / change behavior plus add new function mimicking current behavior / change docs plus add new function with my preferred behavior.)

[ChickenProp]

Ah geez. I just saw #281 and #282 and discovered

• Yes, this is deliberate behavior.
• The behavior I want already exists, with my exact implementation! It's filterT. It just isn't documented.

So, documentation-improving PR is coming up.