proposition: Lemma genRBTree_height_eq (hc : nat*color) : genRBTree_height hc = match hc with | (0, Red) => returnGen Leaf | (0, Black) => oneOf [returnGen Leaf; (do! n <- arbitrary; returnGen (Node Red Leaf n Leaf))] | (S h, Red) => liftGen4 Node (returnGen Black) (genRBTree_height (h, Black)) arbitrary (genRBTree_height (h, Black)) | (S h, Black) => do! c' <- genColor; let h' := match c' with Red => S h | Black => h end in liftGen4 Node (returnGen c') (genRBTree_height (h', c')) arbitrary (genRBTree_height (h', c')) end.
proof: Proof. unfold_sub genRBTree_height (genRBTree_height hc). f_equal. destruct hc as [[|h] [|]]; try reflexivity. f_equal. apply functional_extensionality => [[|]]; reflexivity. Qed.
imports: QuickChick(QuickChick Generators) Lia mathcomp(ssreflect ssrnat ssrbool eqtype) QuickChick.RedBlack(redblack) List String Relations Wellfounded Lexicographic_Product Program.Wf FunctionalExtensionality