How to accumulate a list of FsCheck generators into a single value?

Question

I wrote an FsCheck generator that yields random glob syntax patterns (e.g. a*c?) along with a random string that matches the pattern (e.g. abcd). However my solution uses a mutable variable and I'm rather ashamed of that. Have a look:

open FsCheck

type TestData = {Pattern: string; Text: string}

let stringFrom alphabet =
    alphabet |> Gen.elements |> Gen.listOf |> Gen.map (List.map string >> List.fold (+) "")

let singleCharStringFrom alphabet =
    alphabet |> Gen.elements |> Gen.map string

let matchingTextAndPatternCombo = gen {    
    let toGen = function
        | '*' -> stringFrom ['a'..'f']
        | '?' -> singleCharStringFrom ['a'..'f']
        | c -> c |> string |> Gen.constant

    let! pattern = stringFrom (['a'..'c']@['?'; '*'])
    let mutable text = ""

    for gen in Seq.map toGen pattern do
        let! textPart = gen
        text <- text + textPart

    return {Pattern = pattern; Text = text}
}

Notice that text is mutable and how its value is accumulated in a loop.

My guts tell me that there must be a way to fold the generators into text, but I can't figure how, because I don't understand how let! works under the hood (yet). I was considering something similar to the following:

let! text = pattern |> Seq.map toGen |> Seq.fold (?) (Gen.constant "")

Am I on the right track? What should the accumulator and seed for fold look like?

Answer 1

Your intuition that something like fold could be used here is right, but the problem is that you'd need a version of fold where the folding function returns Gen<'T> computation - so normal List.fold from F# will not work. In this case, I think using mutation is perfectly fine - your code looks pretty clear to me.

Looking through the functions in the Gen module, I do not see a version of fold, but I think Gen.sequence lets you do what you need nicely:

let! textParts = Gen.sequence (Seq.map toGen pattern)
let text = String.concat "" textParts

The Gen.sequence function takes a list of generators and returns a generator that generates a list of values using those generators - this way, you can generate all text parts at once and then just concatentate the results.

If you wanted to write your own fold and use that, it would look something like this:

let rec fold f init xs = gen {
  match xs with
  | [] -> return init 
  | x::xs -> 
      let! state = f init x
      return! fold f state xs }

The code to fold generators would then be:

let! text = 
  Seq.map toGen pattern |> List.ofSeq |> fold (fun (text:string) g -> gen {
    let! textPart = g
    return text + textPart }) ""

I have not tested this, so there may be bugs (most likely, it folds the wrong way round and so you'll end up with reversed strings), but the general structure should be right.