Test that correct overloads are used

[cmeeren]

Forked out from #288 (comment)

In that issue it seems to be a slight worry that generic operators like filter, map, choose etc. may not call the most optimal overloads. This worry is based on the fact that the Seq can or could subsume calls using array, List, Set, etc.

One example of where this is particularly important is length, where Seq.length is O(N) but Array.length is O(1), so if you call length myArray then you want to be absolutely sure that you are in practice calling Array.length, not Seq.length. This is just an important example though; AFAIK the built-in Array.choose, Array.map etc. have better performance than Seq.choose, Seq.map etc. (e.g. less allocations and better cache locality) and thus the correct overload should always be used even though the actual time complexity may be the same.

The goal is that users of FSharpPlus must be able to rely on the correct overload being called without thinking about subsumption etc. In concrete terms, when they pass a List, Set, array or anything else to a generic operator like filter, map, choose, etc., then the overload that is used should be the one that calls List.filter, Set.map, Array.choose etc. and not Seq.filter, Seq.map, and Seq.choose.

There should ideally be automated tests for this, and it should be clearly documented that users can rely on this.

[gusty]

@wallymathieu I think this feature is independent of the F#+ version. Isn't it?

[wallymathieu]

Should be. It would be nice to have it verified for both the 1 and 2 versions.

[gusty]

The key question here is, how do we implement this?

I can think of:

• Adding straight F# conditionals like #if test .. #endif but it would increase a lot the lines of code and force our source to lose the alignment, which is great to to massive updates and to visualize the difference between overloads. What we could do, is to add the effect only on the defaults, to reduce the noise.

• Adding a comment with a specific convention, like (* effect #1 *) which we can expand to something like effects.add "#1" but it will complicate the build process for the tests.

• Adding in internals an operation using conditionals, which in Release mode is a NOP that we know the optimizer will take it away.

Other ideas?

[wallymathieu]

One way to do it would be to inspect compiled usage in order to verify that the correct overload has been chosen by the compiler.

[gusty]

Implemented in #557