Making an FsCheck generator for a recursive record

Question

I have recursive types like this:

type QueryInfo =
   { Title     : string
     Check     : Client -> bool
     Positive  : Decision
     Negative  : Decision }

 and Decision = 
    | Result of string
    | Query  of QueryInfo

I am going to make a generator for FsCheck. I have seen this and I am not interested in approaches like static member. My main problem is that every field has a different type.

FsCheck can already generate values of QueryInfo, but since the type is recursive, the generated values can become so deeply nested that generation of values effectively never stops (or, at least) is very slow.

Answer 1

Something like this ought to work:

let qi =
    let createQi t c p n = {
        Title = t
        Check = c
        Positive = p
        Negative = n }
    let makeQiGen =
        Gen.map4 createQi Arb.generate<string> Arb.generate<Client -> bool>
    let resultGen = Arb.generate<string> |> Gen.map Result
    let rec qi' size =
        if size <= 0
        then makeQiGen resultGen resultGen
        else
            let subQi = qi' (size - 1) |> Gen.map Query
            Gen.oneof [
                makeQiGen resultGen resultGen
                makeQiGen subQi subQi
                makeQiGen resultGen subQi
                makeQiGen subQi resultGen ]
    Gen.sized qi'

The essence is to prevent infinite (or very deep) recursions, which is done by Gen.sized.

When size reaches 0, the generator always returns a leaf node - that is: both Positive and Negative are Result values.

When size is greater than 0, the generators picks from one of four generators:

• One that generates a leaf
• One that generates a new node where both Positive and Negative are new Query values.
• One where Positive is a Result, but Negative is a Query.
• One where Positive is a Query, but Negative is a Result.

In each recursion, though, size is decremented, so eventually, a leaf node is returned.

This answer is based on the Generating recursive data types section of the FsCheck documentation.