Improve Gen.list by only testing [] once

[TysonMN]

I want to improve Gen.list. Actually, what I really want to do is (better) understand Gen.list, and I will be more motivated to do this by having a specific goal to improve it.

Below is code that (if you are lucky) has the following output. It shows that [] is tested many times. Maybe I can figure out how to remove the repeated tests of [].

Requiring luck to investigate this issue slows down progress, so it would be nice if #320 were resolved first.

[0; 1]
├-[]
├-[1]
| ├-[]
| └-[0]
|   └-[]
├-[0]
| └-[]
└-[0; 0]
  ├-[]
  ├-[0]
  | └-[]
  └-[0]
    └-[]

Here is the shrink tree that I desire.

[0; 1]
├-[]
├-[1]
| └-[0]
├-[0]
└-[0; 0]
  ├-[0]
  └-[0]

Even though [0] is also tested twice, my currently feeling is that it is not reasonable to remove that duplication. That comes from either removing the element at index 0 or the element at index 1. Because both elements are 0, both sublists are the same.

let sample =
  Range.constant 0 1
  |> Gen.int32
  |> Gen.list (Range.constant 0 2)
  |> Gen.sampleTree 0 1
  |> Seq.head
  |> Tree.map (sprintf "%A")
  |> Tree.render
printf "%s" sample

[TysonMN]

As a secondary goal, I want to generalize this code slightly so that I can also use it to generate multi-dimensional arrays. The code I recently wrote for multi-dimensional arrays first picks the size and then picks the entries, so after some entry is shrunk, the size will never be shrunk again.

[TysonMN]

[0; 1]
├-[]
├-[1]
| └-[0]
├-[0]
└-[0; 0]
  ├-[0]
  └-[0]

Even though [0] is also tested twice, my currently feeling is that it is not reasonable to remove that duplication. That comes from either removing the element at index 0 or the element at index 1. Because both elements are 0, both sublists are the same.

Oh, but actually [0] can be tested there three times and two of those times are duplicates: twice the sublist [0] obtained by dropping the element at index 1 is tested. It seems possible to me that that can be avoided.

[cmeeren]

I can understand testing [] only once if it's the only generated value, but what if you are generating other values in the same property? Then [] could be generated multiple times and combined with several other values, which is desirable.

The general idea, I think, is to not generate the same combination of values in the entire property (considering all generators that are used in the property). (Whether it is desirable to optimize that away, is another matter.)