Created
November 28, 2024 18:42
-
-
Save cxandru/c9bf9165ab753d2c57e00e8c3b97d947 to your computer and use it in GitHub Desktop.
Generator for valid Binary Search Trees (BSTs) for property-based testing using FSharp's FsCheck framework
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| module GenerateYourNeighbors | |
| open FsCheck | |
| type BST<'a> = | |
| | Empty | |
| | Node of BST<'a> * 'a * BST<'a> | |
| [<StructuralEquality;StructuralComparison>] | |
| type Extended<'a when 'a: comparison> = | |
| | NegInfty | |
| | Just of 'a | |
| | PosInfty | |
| type ValidBST<'a> = Valid of BST<'a> | |
| type InvalidBST<'a> = Invalid of BST<'a> | |
| let genInRange : (Extended<int> * Extended<int>) -> Gen<int> = function | |
| | Just lo , Just hi -> Gen.choose(lo, hi) | |
| | NegInfty, Just hi -> Gen.filter (fun x -> x <= hi) Arb.generate | |
| | NegInfty, PosInfty-> Arb.generate | |
| | Just lo, PosInfty -> Gen.filter (fun x -> x >= lo) Arb.generate | |
| | _ -> failwith "purposely no pattern for(_,-∞)" | |
| // Generator for valid BST with given depth and bounds (for an a priori unbounded one, use `genenerateValidBST (NegInfty, PosInfty)`) | |
| // inspired by Section 4. "Why Measure When You Can Require?" of "How to keep your Neighbours in Order" (Conor McBride, 2014) | |
| let rec generateValidBST (size : int) (range : Extended<int> * Extended<int>) : Gen<BST<int>> = | |
| if size <= 0 then Gen.constant Empty | |
| else (gen { | |
| let (lo, hi) = range | |
| let! p = genInRange(range) | |
| let! sizeL = Gen.choose(0, size - 1) | |
| let! sizeR = Gen.choose(0, size - 1) | |
| let! l = generateValidBST sizeL (lo, (Just p)) | |
| let! r = generateValidBST sizeR ((Just p), hi) | |
| return Node (l, p, r) | |
| }) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment