I doubt that was what was going on, but I can't find any documentation right now on how F# optimizes case matches. If it was doing that, it would have to apply those classes to all instances of the patterns, which seems unlikely in the face of separate compilation as "Foo of int * bool * string" could be constructed in a far away place. Well, if Foo was a local type that wouldn't escape, perhaps they could optimize it in the module, but it still seems unlikely.

OO languages have trouble optimizing constructs such as interfaces (and other forms of multiple inheritance) because the v-table is no longer very linear. Now throw in arbitrary predicates and you are pretty much back to linear search. Probably the state of the art can be found in GHC, but even they probably fall back to linear in a lot of cases.