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?

Answer 1

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)
  }