Limit recursion depth based on size instead of configuration value

[TysonMN]

PR #21 added a configuration value called RecursionDepth to prevent stack overflows when generating a recursive type (c.f. #19 (comment)).

FsCheck solves this problem by relating the recursion depth to the size parameter.

However, a recursive generator like this may fail to terminate with a StackOverflowException, or produce very large results. To avoid this, recursive generators should always use the size control mechanism

This seems like a better solution to me, but I am just getting seriously into property-based testing, so I am probably unaware of all the considerations.

What are the tradeoffs for this configuration value vs utilizing the size parameter?

[cmeeren]

I have no idea; @moodmosaic?

[moodmosaic]

The sized approach of FsCheck is more elegant since you can use the size parameter via Gen.sized to control the depth (instead of introducing another variable).

[moodmosaic]

Some thoughts around the size, in general: hedgehogqa/haskell-hedgehog#38 (comment)

[TysonMN]

That is what I expected.

@cmeeren, how do you feel about removing RecursionDepth and instead bounding recursive generation with the size parameter?

I am interested to implement this simply because I think it might be a good challenge for me.

[TysonMN]

Some thoughts around the size, in general: hedgehogqa/haskell-hedgehog#38 (comment)

Yes, I really like the Range concept. I think it is very clear...after @cmeeren first explained to me in elmish/Elmish.WPF#240 (comment) and then especially after watching the video @moodmosaic linked to in hedgehogqa/fsharp-hedgehog#182 (comment).

[cmeeren]

@cmeeren, how do you feel about removing RecursionDepth and instead bounding recursive generation with the size parameter?

I'm happy to use size to control the recursion depth, but perhaps we should have a MaxRecursionDepth so that users have some control. Too much recursion in auto-generation can substantially increase the test run time. What do you think?

[moodmosaic]

so that users have some control

They’ll have that control through the size... What happens when size > MaxRecursionDepth?

[cmeeren]

They’ll have that control through the size...

How so? Isn't size automatically incremented from 0 to 99 or something like that based on the test that is run?

[moodmosaic]

Yes, but you can interpret it (in this case) any way you want, e.g. halve it on each recursion (as FsCheck mentions in the docs).

[cmeeren]

Ok. (For reference, here's the mentioned docs.)

I won't be able to work on this, but I'm more than happy to take a PR that makes sure that auto-generating recursive types aren't unnecessarily slow (i.e., be conservative with the defaults, e.g. exponential with a max depth of, say, 3? Open to suggestions), and gives the user some kind of control over the recursion depth. The readme should have an example of how to control it.