How to recursively use FsCheck generators?

Question

I use FsCheck for property-based testing, so I defined a set a generators for custom types. Some of types are composed of others, and there are generators for all of them. Having defined a generator for Alphanumeric type, I want to define a generator for RelativeUrl type, and RelativeUrl is list of 1-9 Alphanumeric values separated by slash symbol. Here's the definition that works (Alpanumeric has "Value" property that converts it to String):

static member RelativeUrl() =
    Gen.listOfLength (System.Random().Next(1, 10)) <| Generators.Alphanumeric()
    |> Gen.map (fun list -> String.Join("/", list |> List.map (fun x -> x.Value)) |> RelativeUrl)

Even though it's quite simple I don't like that I use Random.Next method instead of using FsCheck random generators. So I tried to redefine it like this:

static member RelativeUrl_1() =
    Arb.generate<byte> 
    |> Gen.map int 
    |> Gen.suchThat (fun x -> x > 0 && x <= 10)
    |> Gen.map (fun length -> Gen.listOfLength length <| Generators.Alphanumeric())
    |> Gen.map (fun list -> String.Join("/", list))

Compiler accepts it but in fact it's wrong: a "list" in the last statement is not a list of Alphanumeric values but a Gen. Next attempt:

static member RelativeUrl() =
    Arb.generate<byte> 
    |> Gen.map int 
    |> Gen.suchThat (fun x -> x > 0 && x <= 10)
    |> Gen.map (fun length -> Gen.listOfLength length <| Generators.Alphanumeric())
    |> Gen.map (fun list -> list |> Gen.map (fun elem -> String.Join("/", elem |> List.map (fun x -> x.Value))  |> RelativeUrl))

But this doesn't work either: I am getting back Gen of Gen of RelativeUrl, not Gen of RelativeUrl. So what would be a proper way of combining generators at different levels?

Instead of using System.Random, can't you use Gen.choose? — Mark Seemann
@MarkSeemann, you can use choose instead of Random by instantly sampling it, but that would defeat the purpose, because this choose won't be part of the resulting generator, but will work as a sort of utility function. No better than Random, really. — Fyodor Soikin
@FyodorSoikin I disagree - you never want to use System.Random in generators because it will destroy reproducibility (i.e. same seed returns different results each time) and make shrinking impossible (or at least non-deterministic). — Kurt Schelfthout
@KurtSchelfthout: Mark suggested to use Gen.choose instead of Random. If you plug it in place of Random in the OP's first code block, it would be useless, would it not? — Fyodor Soikin
@FyodorSoikin Just read your comment again - yes, if you use Gen.choose |> Gen.sample it's no better than Random. But don't think that's what @MarkSeemann meant :) Confusion all round...but I think we are all saying the same thing. — Kurt Schelfthout

Fyodor Soikin Fyodor Soikin · Accepted Answer · 2016-03-31T13:57:20

Gen.map has the signature (f: 'a -> 'b) -> Gen<'a> -> Gen<'b> - that is, it takes a function from 'a to 'b, then a Gen<'a>, and returns a Gen<'b>. One might think of it as "applying" the given function to what's "inside" of the given generator.

But the function you're providing in your map call is, in fact, int -> Gen<Alphanumeric list> - that is, it returns not some 'b, but more specifically Gen<'b>, so the result of the whole expression becomes Gen<Gen<Alphanumeric list>>. This is why Gen<Alphanumeric list> shows up as the input in the next map. All by design.

The operation you really want is usually called bind. Such function would have a signature (f: 'a -> Gen<'b>) -> Gen<'a> -> Gen<'b>. That is, it would take a function that produces another Gen, not a naked value.

Unfortunately, for some reason, Gen doesn't expose bind as such. It is available as part of the gen computation expression builder or as operator >>= (which is de facto standard operator for representing bind).

Given the above explanation, you can rephrase your definition like this:

static member RelativeUrl_1() =
    Arb.generate<int> 
    |> Gen.suchThat (fun x -> x > 0 && x <= 10)
    >>= (fun length -> Gen.listOfLength length <| Generators.Alphanumeric())
    |> Gen.map (fun list -> String.Join("/", list))

You may also consider using a computation expression to build you generator. Unfortunately, there is no where defined for the gen expression builder, so you still have to use suchThat to filter. But fortunately, there is a special function Gen.choose for producing a value in a given range:

static member RelativeUrl_1() =
  gen {
    // let! length = Arb.generate<int> |> Gen.suchThat (fun l -> l > 0 && l <= 10)
    let! length = Gen.choose (1, 10)
    let! list = Gen.listOfLength length <| Generators.Alphanumeric()
    return String.Join ("/", list)
  }

How to recursively use FsCheck generators?

2 Answers