FsCheck custom generator of lists satisfying a predicate

Question

For a given predicate pred : 'a list -> bool and generator gen : Gen<'a>, consider the following generator of well-formed lists that satisfy the predicate:

let wellFormedList pred gen =
   Gen.ofList gen
   |> Gen.filter pred

As mentioned in the FsCheck manual, there should be a high chance that predicate holds for a random list. Unfortunately, this assumption does not hold in my case. Thus, I need te define a custom generator for lists that satisfy the predicate.

How can I define a custom generator that starts from the empty list and extends it with new random elements, until the list satisfies the predicate?

I probably need to use the computation expression gen { } for generators, but I do not see how.

PS: I am aware that, unlike the original implementation of wellFormedList, the distribution of such a custom generator is not uniform over all lists that satisfy the predicate.

Can we assume from your question that a list that doesn't satisfy the predicate just needs more random elements added until it does? There's no need to throw out a list that doesn't satisfy the predicate, we should just append more elements to it? — Nathan Wilson

Nathan Wilson Nathan Wilson · Accepted Answer · 2019-03-22T16:54:17

Well if I'm understanding it right, I think this should do it:

let wellFormedList (predicate:'a list -> bool) (myGen:Gen<'a>) = 
  gen {
    let! initialList = Gen.listOf myGen
    let mutable myList = initialList
    while not <| predicate myList do
      let! newVal = myGen
      myList <- (newVal :: myList)

    return myList      
  }

or if you wanted a recursive function:

let wellFormedList (predicate:'a list -> bool) (myGen:Gen<'a>) = 
  gen {
    let rec addIfNecessary listSoFar =
      if predicate listSoFar 
      then gen { return listSoFar }
      else gen { 
        let! newVal = myGen
        return! addIfNecessary (newVal :: listSoFar)
      }

    let! initialList = Gen.listOf myGen
    return! addIfNecessary initialList
  }

I haven't checked what kind of distributions that gives you though. And of course you risk an infinite loop (or stack overflow) if the list never converges on a form that passes the predicate.

FsCheck custom generator of lists satisfying a predicate

1 Answers