Implement property expression à la Hedgehog

[cmeeren]

One thing that pains me in FsCheck as compared to Hedgehog is generating values. In Hedgehog, for a suitably defined G.int (generates ints without any more fuss) and G.sortTuple3 (sorts a 3-tuple) I can do this:

[<Fact>]
let ``constrain returns original value if inside interval`` () = 
  Property.check <| property {
    let! x1, x, x2 = G.int |> Gen.tuple3 |> G.sortTuple3
    test <@ constrain (x1, x2) x = x @> }

In FsCheck, for a suitably defined G.sortTuple3, this looks much worse, even without a shrinker:

[<Property>]
let ``constrain returns original value if already inside interval`` () =
  Arb.generate<int*int*int>
  |> Gen.map G.sortTuple3
  |> Arb.fromGen
  |> Prop.forAll <| fun (x1, x, x2) ->
    test <@ constrain (x1, x2) x = x @>

I have a few hundred other tests that also point in the same direction: Using a computation expression for properties that allows you to generate values directly inside the property looks much clearer. Could such a computation expression be implemented in FsCheck?

Or perhaps I have missed some other nicer way to accomplish this in FsCheck?

[ploeh]

Computation expressions can only be created for monads, because you need a Bind operation to support let! bindings.

Unfortunately, Arbitrary<T> is not a monad, because the shrinker isn't a functor. (IIRC, the problem is that the shrinker is both co- and contravarient, because the generic type appears both as input and output.)

[cmeeren]

I'd be very happy to have this work just for generators, without shrinking.

[ploeh]

You can use the gen computation expression for that, but then you're going to need to turn it into an Arbitrary<'a> with Arb.fromGen...

[cmeeren]

Yes, and it's also a pain (or at the very least messy) if you need values from several generators.

[kurtschelfthout]

I don't think there is any technical roadblock. Prop.forAll is essentially bind, and Property is essentially Gen which is a computation expression. I'm not convinced about the "looks much worse" bit. Here's how I would write it. I specifically like to give Arbitrary instances explanatory names that read nicely inside a forall:

[<Property>]
let ``constrain returns original value if already inside interval`` () =
  let sortedTuples = Arb.generate<int*int*int> |> Gen.map G.sortTuple3 |> Arb.fromGen
  Prop.forAll sortedTuples (fun (x1, x, x2) ->  test <@ constrain (x1, x2) x = x @>)

[cmeeren]

Thanks for the tip, that looks better and would certainly scale a bit better with regards to the number of generated values needed (though not that much as far as I can see, since you'd need to zip the generators together).

I'm still more a fan of generating values using let! syntax in a computation expression, since this would (ideally) get rid of some boilerplate like Arb.fromGen, Prop.forAll, intermediate names (sortedTuples), and the inner fun definition. And this is boilerplate on more or less every single test. Plus the zipping of generators whenever you need values from more than one generator.

[kurtschelfthout]

You just get other "boilerplate" in return like let! ... = ..., and property { .... The two examples are about the same size. You could get rid of the sortedTuples using the |> <| syntax trick, but I like naming things.

Also you can do

[<Property>]
let ``constrain returns original value if already inside interval`` (t3) = 
    let (x1, x, x2) = G.sortTuple3 t3
    test <@ constrain (x1, x2) x = x @>

With shrinking.

We'll need more substantial examples than this.

[cmeeren]

Also you can do [snip] with shrinking.

Ooh, nice! I totally missed that. For this example, at least. :)

I'll see if I can come up with some real examples that are more revealing. If I can't, it may all just be in my head - you never know with people these days.

[kurtschelfthout]

A cute idea I just had to share:

let (|SortedTuple|) = G.sortTuple3

[<Property>]
let ``constrain returns original value if already inside interval`` (SortedTuple (x1,x,x2)) = 
    test <@ constrain (x1, x2) x = x @>

[cmeeren]

Just a quick sanity check here: Consider the following code:

let increasing3<'a when 'a : comparison> = 
  Arb.from<'a*'a*'a> |> Arb.filter (fun (x1, x2, x3) -> x1 < x2 && x2 < x3)

[<Property>]
let ``returns upper value if above interval`` () =
  increasing3<int> |> Prop.forAll <| fun (x1, x2, x) ->
  test <@ constrain (x1, x2) x = x2 @>

I can see exactly two ways of achieving this:

1. As above, use prop.forAll, referencing the explicit arbitrary
2. Create a single-case DU wrapper and register the arbitrary, allowing you to take the wrapper type as a parameter to the test function

Am I right in that there are no other ways to do this?

[cmeeren]

And one other question for the same code snippet: Although it might not be needed in this particular case, in order to decrease the chance of throwing away results I considered sorting the tuple (as previously mentioned) before Arb.filter, but of course there is no Arb.map, only Arb.convert. Would it generally mess with shrinking if I use Arb.convert sort3 id, i.e. changing the element order on generation, but not shrinking?

Edit: I discovered Arb.mapFilter, which solves the problem and also taught me (I think) that yes, this will be a problem. Using Arb.convert sort3 id as mentioned, the values would be reduced in a manner that does not guarantee their order. Here's my current solution:

let sort3 (x1, x2, x3) =
  [x1; x2; x3] |> List.sort |> (fun [x1;x2;x3] -> x1, x2, x3)

let isSorted3 (x1, x2, x3) =
  x1 <= x2 && x2 <= x3

let isStrictlyIncreasing3 (x1, x2, x3) =
  x1 < x2 && x2 < x3

let increasing3<'a when 'a : comparison> = 
  Arb.from<'a*'a*'a>
  |> Arb.mapFilter sort3 isSorted3 // for efficiency
  |> Arb.filter isStrictlyIncreasing3

I guess I could also have used Arb.convert sort3 sort3.

Another edit: Now I'm having trouble reproducing the example that led me to this conclusion. Maybe I haven't understood it after all.

[cmeeren]

Okay, here's an example: Combining arbitraries. Say I want a test that needs two distinct integers and a string. I have already defined the following:

let distinct2<'a when 'a : equality> =
  Arb.from<'a*'a> |> Arb.filter (fun (x1, x2) -> x1 <> x2)

let alphaNumStr =
  let alphaNum = ['A'..'Z'] @ ['a'..'z'] @ ['0'..'9']
  Arb.from<string>
  |> Arb.filter (fun s -> s |> Seq.forall (fun c -> alphaNum |> List.contains c))

Now, how do I combine these? I can't find any way of doing that (there might be an easy way I don't know - nothing would be better). The following obviously doesn't work, but serves to illustrate what I want:

[<Property>]
let ``what is supposed to happen should happen`` () =
  Prop.forAll (distinct2<int>, alphaNumStr) <| fun (x1, x2) s
  ...

These arbitraries are fairly simple, but one could easily imagine the need for combining more complex ones.

With computation expressions, this is trivial, since each arbitrary (or generator) would be at the right side of a separate let! binding.

[kurtschelfthout]

Am I right in that there are no other ways to do this?

You could use ==> instead of Arb.filter.

[<Property>]
let ``returns upper value if above interval`` (x1,x2,x) =
   x1 < x2 && x2 < x ==> lazy(  test <@ constrain (x1, x2) x = x2 @> )

[kurtschelfthout]

although it might not be needed in this particular case, in order to decrease the chance of throwing away results I considered sorting the tuple (as previously mentioned) before Arb.filter

Yes, that's exactly what Arb.mapFilter is for. I would not advise using Arb.convert, that's really intended for bijective conversions. Though I guess it might work, sort of.

[kurtschelfthout]

Now, how do I combine these?

[<Property>]
let ``what is supposed to happen should happen`` () =
  Prop.forAll distinct2<int> (fun x1 ->
  Prop.forAll alphaNumStr (fun x2 ->
     s
   ))

This also shows that Prop.forAll is basically bind.

[cmeeren]

Oh. Well then. Didn't think of that 🙃 Thanks!

[cmeeren]

But defining nested functions (or in general, nested constructs) like that, isn't that exactly what computation expressions are for? I'm open to this being subjective, but I would say that for any such case where you need to use multiple arbitraries, it's definitely cleaner to say

[<Property>]
let ``what is supposed to happen should happen`` () = property {
    let! x1, x2 = distinct2<int>
    let! s = alphaNumStr
    ... }

instead of

[<Property>]
let ``what is supposed to happen should happen`` () = 
  Prop.forAll distinct2<int> <| fun (x1, x2) ->
  Prop.forAll alphaNumStr <| fun s ->
  ...

I would also say it's easier to newcomers. I'm giving an F# course at my workplace today, and I would find it much easier to explain the first one, which lets you use normal F# syntax as long as you wrap it in property { } and use let! when generating, than the second one, which has more noise and require more knowledge of indenting rules ("why don't you have to indent the nested functions?"), the backward pipe operator (or using more messy parentheses), and the question of why nested functions are at all needed.

Note by the way that I haven't included any other boilerplate than property { } in the first example. Contrary to Hedgehog (which requires Property.check somewhere), I assume this would be handled by FsCheck.Xunit.

[kurtschelfthout]

But defining nested functions (or in general, nested constructs) like that, isn't that exactly what computation expressions are for?

They're syntactic sugar for nested functions, when they are needed for monadic binds. I feel that forAll <set of values> <value -> assertion> conveys intent better than let! value = <set of values>; <assertion>, and I don't really mind the nesting or the parenthesis, because it's rare that the level of nesting is deep. That is a matter of taste to some extent.

What isn't a matter of taste is that using computation expressions carries performance penalties that are non-obvious - extra Delay and Run calls and closures are generated. Bind, or let! is often the only mechanism used and is in many cases not necessary (i.e. you could use map, where or apply instead which are much lighter weight). They don't work well with operations like sequence and .&..

[cmeeren]

I didn't know about the performance impacts. Out of interest, do you have any ballpark estimate of how large they'd be in this context?

I also agree that forAll better conveys the intent. It's just a tad bit more syntactically heavy than I feel entirely comfortable defending to my colleagues.

In any case, feel free to close this if you don't want to implement it. :-)

[kurtschelfthout]

Yes I don't think it's worth the work in v2. If #403 works out in v3, I expect you get this as well.