Support `Gen.pick` by analogy to `Seq.pick`

[brianberns]

Seq.pick is a very useful function that applies a given "chooser" function to successive elements, returning the first x where the function returns Some x. By analogy, I think FsCheck should provide a similar function. Here's a simple implementation that demonstrates the idea:

let rec pick chooser gn =
    gen {
        let! value = gn
        match chooser value with
            | Some v -> return v
            | None -> return! pick chooser gn
    }

[kurtschelfthout]

Appreciate the idea @brianberns. I understand the utility of pick (combining transformation with filtering), but a few thoughts on the "cost" side of the equation.

Implementation wise, would something like Gen.map chooser >> Gen.filter Option.isSome >> Gen.map Option.get work? That seems relatively straightforward to implement.

The situation in FsCheck is a bit more complicated than for Seq - there are safeguards when doing any kind of filtering to make sure you don't lose time generating elements that don't pass the filter. I've been tripped by this plenty of times, so filtering in general is not encouraged in FsCheck. It's much better to create "good" elements by construction or transformation. Filtering of course has some utility, e.g. to filter out zeroes or single elements from a wide range, but certainly less utility than Seq.filter/pick.

Lastly, for Gen.filter there is the alternative Gen.tryFilter https://fscheck.github.io/FsCheck/reference/fscheck-gen.html#tryFilter to increase the size if a number of elements don't pass the filter. Do we need tryPick?

With all that (ease of implementation + likely problematic in common use cases + non-trivial API impact), do you still feel the added utility outweighs the cost?

[brianberns]

Thank you for the thoughtful response.

Implementation wise, would something like Gen.map chooser >> Gen.filter Option.isSome >> Gen.map Option.get work?

I tend to avoid Option.get and repeated calls to map as code smells, but I don't have a strong opinion on this. As a user, I'm more interested in the API than the implementation.

filtering in general is not encouraged in FsCheck

I definitely agree with this. However, there are cases where it can't reasonably be avoided. In those cases, I think it makes sense to think of a generator as producing a stream of potential values, much like Seq.

Do we need tryPick?

Yes, if you decide to include pick in the API, then I think it makes sense to provide tryPick as well.

[ploeh]

I'm fairly agnostic about this suggestion, but tend to agree with @kurtschelfthout that filtering should be avoided in most cases. (And then there are some rare cases where it makes sense.)

filtering in general is not encouraged in FsCheck

I definitely agree with this. However, there are cases where it can't reasonably be avoided.

I tend to be curious when encountering claims like that. This may risk derailing the discussion, but would you mind sharing an example?

[brianberns]

Sure. I'm working on a compiler that does type inferencing, which relies on a unification algorithm. Two types can be unified if there is a substitution that can be applied to both types to make them equal. My unit test generates pairs of types that can be unified and then verifies that the substitution does indeed produce equal types. I don't know how to do this constructively (i.e. without filtering), but I'm certainly open to suggestions.

[ploeh]

That's what I get for asking 😅 That's not really in my wheelhouse, but in any case it's hard to suggest alternatives without code.