compare working differently with generics involved

Question

I stumbled upon some "odd behaviour". I was using the F# interactive to test some code and wrote

Seq.zip "ACT" "GGA" |> Seq.map ((<||) compare)
// val it : seq<int> = seq [-1; -1; 1]

Then I wanted to make a function out of it and wrote

let compute xs ys = Seq.zip xs ys |> Seq.map ((<||) compare)
// val compute : xs:seq<'a> -> xs:seq<'a> -> seq<int> when 'a : comparison

That generalized the first snippet of code and I thought that was a good thing... until I tried to use it

compute "ACT" "GGA"
// val it : seq<int> = seq [-6; -4; 19]

So somehow compare acts differently for the "same thing" when there is a different "point of view" (explicit type vs generics)

I know how to solve it: either by making the type explicit

let compute (xs: #seq<char>) // ... or char seq or string

Or keeping the type generic and composing with the sign function

let compute (* ... *) ((<||) compare >> sign)

tl;dr the question is where does the difference in behavior come from exactly?

Answer 1

This is an intricate interplay between F# compiler optimization and .NET standard library optimization.

First, F# tries hard to optimize your program. When the types are known at compile time, and the types are primitive, and comparable, then the call to compare gets compiled to just straight up comparison. So comparing the characters in your example would look like if 'A' < 'G' then -1 elif 'A' > 'G' then 1 else 0.

But when you wrap the thing in a generic method, you take away the type information. The types are generic now, the compiler doesn't know that they are char. So the compiler is forced to fall back to calling HashCompare.GenericComparisonIntrinsic, which in turn calls IComparable.CompareTo on the arguments.

And now guess how IComparable is implemented on the char type? It simply subtracts the values and returns the result. Seriously, try this in C#:

Console.WriteLine( 'A'.CompareTo('G') ); // prints -6

Note that such implementation of IComparable is not technically a bug. According to the documentation, it doesn't have to return only [-1,0,+1], it can return any value so long as its sign is correct. My best guess would be that this is also done for optimization.

F# documentation for compare doesn't specify this at all. It just says "result of the comparison" - go figure what that's supposed to be :-)

---

If you want your compute function to return only [-1,0,+1], that can be easily achieved by making the function inline:

let inline compute xs ys = Seq.zip xs ys |> Seq.map ((<||) compare)

Now it will get expanded at call site, where the types are known, and the optimized code can be inserted. Keep in mind though that, since [-1,0,+1] behavior is not guaranteed in the docs, it may disappear in the future. So I would rather not rely on it.