Generate lazily evaluated sequences

[cmeeren]

When writing tests for Hedgehog.Experimental I came across the need for just checking if a property holds at least some of the time. For example, when testing withNull, I create a property I run once that generates a list of, say, 1000 items and checks if it contains null.

When testing if a property holds some of the time, one might need to generate many items to avoid false negatives. But most of the time you might get a positive fairly quickly, say after 10 items and the rest of the 990 generated items are wasted. I thought about using Gen.seq instead of Gen.list, but it just generates a list and passes it to Seq.ofList and thus provides no performance benefits.

Is it possible to have Gen.seq actually generate a lazily evaluated sequence?

[moodmosaic]

Perhaps with a custom generator seq 'a that uses sequence expressions internally?

[cmeeren]

I hope that's possible, but I don't know how. AFAIK you can't easily mix computation expressions.

[Porges]

Maybe we could invent some kind of ... computation expression transformer 😉

[moodmosaic]

Sure! A computation expression (CE) is really a class (a type that represents objects that can have properties, methods, and events).

So it should be possible to define a CE with a non-parameterless constructor taking another CE as a parameter, similar to this one.

[TysonMN]

It is easy to lazily obtain a given number of values from some generator. However, I don't know how to create Gen<seq<'a>> in which the generated sequences are lazy. The difference between these two statements is (integrated) shrinking.
The current implementation to create Gen<List<'a>> converts List<Tree<'a>> to Tree<List<'a>> (which goes by the name sequence in functional programming). Maybe a compromise is that Gen<seq<'a>> would return lazy values before shrinking and lists cast as seqs after shrinking has started. Not sure though. This path is currently unclear to me.

This is the test to which @cmeeren referred. I created this PR to change that test into one that is more efficient and more idiomatic.

[cmeeren]

Thinking about it now, I'm unsure why a generated lazy sequence would be useful. If I read my original comment right, the only benefit is in optimizing positives (i.e. test failures), which is not really useful to optimize.

Edit: Nevermind, I see that for the withNull test this would be useful, since you can stop at the first null.

[TysonMN]

The unusual thing about your use case is that you don't care about shrinking. It is trivial to create a shrunken list that doesn't contain null, namely an empty one. You are trying to verify that a particular distribution contains a certain value in its sample space.

You do this by forcing the list generator to create 1000 values of the underlying generator with the hope that the set of those 1000 values is equal to the set of values in the sample space.

An interesting alternative for an integral (aka discrete) generator is to output a lazy sequence of all values in its sample space. Lazy is necessary here since the sample space might be infinite. In your use case, the sample space is finite, so you could either find null and have the test pass or search the whole sample space without finding null and have the test fail.

[TysonMN]

@cmeeren and I agreed that that PR was not an improvement.

I have a better idea though. The actual problem @cmeeren wants to solve is (almost) exactly what Gen.sample does. I created PR hedgehogqa/fsharp-hedgehog-experimental#42 to make that change.

The only problem is that the return type of Gen.sample is List<'a> instead of seq<'a>. That change it easy though. I can make it after PR #238 is done.