Add AA Tree and tests

[hummy123]

I wasn't able to run the test in this repository as I don't have .NET 6.0.401 SDK installed (only a version matching .NET 7), but I don't expect anything to break since it was just mostly a copy-paste from my other repository.

Appreciate the time taken in reviewing this.

[gdziadkiewicz]

Checking.

[hummy123]

I think all of these are good suggestions and appreciate your rigorous standards. I'll have them implemented in the next few days hopefully.

[hummy123]

Hi @gdziadkiewicz and thanks again for the feedback. (I personally think it's easier to reply "here" rather than you jumping up/down the page navigating to different comments, but let me know if you prefer the other way of individual threads.)

1. I divided the tests to have one assertion each test and gave more descriptive test names as asked (good idea).
2. I used non-empty assertion messages in my new commit, but to be honest I think the messages I wrote are a bit tautologous with the test's name. (I didn't find much clear guidance on what to write from the other tests here like IntMap.fs but happy to revise them if asked.)
3. I tried to rewrite some/most of the compact tests to use AAA as recommended (good idea again).
4. You suggested using Expect.containsAll for some of the "Conversion from tests" (AaTree.ofList/Array/Seq), which I understand over the for loop that iterates over the input list and asserts AaTree.exists for each of them.
   • I think your way is definitely cleaner, but if we wanted to use Expect.containsAll we would need to use AaTree.toList/Array/Seq to build a list from the tree first.
   • I'm not sure if the mutual recursion with conversion methods (testing ofList with toList) is something I should worry about, but happy to make use of it in the test if asked (we have conversion toList/Array/Seq methods that build a list with of and check the output with to, so I think in that case we would be collapsing the conversion to/from tests since their logic would be exactly the same.
5. It's guaranteed that AaTree's conversion to methods will be sorted, as it does an in-order traversal of the AA Tree.
6. Good point. Replaced with toSeq as suggested, but the :> cast is still there (get a type inference error which I'm not sure how to solve in an OOP-style definition).
7. I haven't really worked with Sequences in F# (kind of new to the language/FP in general), so I don't feel confident writing a lazy toSeq implementation but I think it's a good idea. Happy to replace the current impplementation with your code (although I can't write test for a lazy function because of my inexperience with them).
8. Removed the open for Expecto.Flip as suggested and have the tests running successfully.

[hummy123]

I reviewed my code and compared it with the paper (and also with the Isabelle HOL proof linked below which corrects the paper in a couple of places) and made some changes.

Summary of my mistakes (now fixed):

• My code only called the adjust function when deleting the left child when it should call the function in all cases (less than, greater than, equal).

Summary of changes from the proof (corrects errors in the paper, and corrections now implemented in code):

• The function dellrg which the proof calls split_max recursed the left subtree in the original but is meant to recurse the right sutree.
• Fixed calculation for the nlvl helper function.

Isabelle HOL proof for reference: https://isabelle.in.tum.de/library/HOL/HOL-Data_Structures/AA_Set.html .

[gdziadkiewicz]

@hummy123 the CI build is failing due to problems with code formatting. Could you resolve that?

[hummy123]

@gdziadkiewicz Got it working thanks to your help (haven't used FAKE/GitHub actions much before).

Here's the action running successfully on my own fork: https://github.com/hummy123/FSharpx.Collections/actions/runs/3841007372/jobs/6540731078 .

(Also updated FAKE as it was giving me errors.)

[gdziadkiewicz]

@hummy123 I'm sorry that I'm not able to work on it quicker. Would you mind if I add some property tests to your code and change the toSeq implementation to the one I proposed?

[hummy123]

@gdziadkiewicz No worries - appreciate your time. Anything that makes the code better and tests more resilient sounds good to me, so go ahead.