9

I'm still trying to wrap my head around how F# generalizes (or not) functions and types, and there's a case that's bugging me:

let min(a, b) = if a < b then a else b

let add(a, b) = a + b

let minInt = min(3, 4)
let minFloat = min(3.0, 4.0) // works!

let addInt = add(3, 5)
let addFloat = add(3.0, 5.0) // error: This expression was expected to have type
                             // int but here has type float

Here min has the generic type 'a * 'a -> 'a (requires comparison) while add has a concrete type int * int -> int, apparently inferred from its first use in the program. Both are declared and used in the same way, so why the difference in generalization?

I understand that in the case of add, the problem can be side-stepped by declaring the function inline, which causes it to get a generic type definition, i.e. 'a * 'b -> 'c (requires member (+)), but that doesn't explain why this is needed in this case and not the other.

Asik
  • 21,506
  • 6
  • 72
  • 131
  • 6
    The compiler has abstracted the concept of "comparable"; it has not abstracted the concept of "addable". `<` is the odd one out here, not `+`. – ildjarn May 14 '12 at 19:26
  • Why do you expect uses of `+` and `<` to generate the same signature? – Daniel May 14 '12 at 19:34
  • @Daniel I don't expect the same signature (although in this particular case it would make sense, but that's not the point); I expect that either both should be generic or neither. Here one is concrete and the other is generic without apparent reason. – Asik May 14 '12 at 19:43
  • See this for background: http://stackoverflow.com/questions/10588506/type-inference-functions-vs-types/10588667#10588667 – yamen May 14 '12 at 21:00

3 Answers3

7

There is an excellent write up on this very issue by @TomasP here: http://tomasp.net/blog/fsharp-generic-numeric.aspx

When writing simple generic code that has some type parameter 'T, we don’t know anything about the type parameter and there is no way to restrict it to a numeric type that provides all the operators that we may need to use in our code. This is a limitation of the .NET runtime and F# provides two ways for overcoming it.

But why are < and > (and by extension, =, <= and >=) OK?

The F# compiler treats equality and comparison differently (see section 5.2.10 Equality and Comparison Constraints in the specs, thanks @Daniel). You get the special comparison constraint, which is allowed when (simply, see the spec for more detail):

If the type is a named type, then the type definition does not have, and is not inferred to have, the NoComparison attribute, and the type definition implements System.IComparable or is an array type or is System.IntPtr or is System.UIntPtr.

There is no such special handling for the + operator. Why couldn't there be a constraint such as numeric?

Well isn't that operator also defined for strings? In some languages for lists and collections? Surely it would be an addable constraint and not numeric. Then many such overloaded operators can be found in a program with different semantic meaning. So F# provides a 'catch-all' method with static member constraints and the inline keyword. Only equality and comparison are special.

yamen
  • 15,390
  • 3
  • 42
  • 52
  • So, in general, does F# automatically look for constraints that allow for keeping types generic, or is this specific to a set of pre-defined operators? – Asik May 14 '12 at 20:38
  • In general F# will try and make the types as generic as possible for how they are used. However, it can't cheat the .NET framework and define a generic for the concept of 'number' - there is no relevant interface that it can constrain to! – yamen May 14 '12 at 20:40
  • 2
    @yamen: The `comparison` constraint doesn't generate something like `where T : IComparable` in C#. It exists at compile-time only and is less restrictive. See the [relevant section of the spec](http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/manual/spec.html#_Toc321997037). – Daniel May 14 '12 at 20:45
  • Yes, it's a bit different - but from the spec "it usually implies that a type must implement System.IComparable". I'll update for accuracy. – yamen May 14 '12 at 20:56
  • I mentioned it because it seems to refute the thrust of your answer: that `comparison` is inherent in .NET and math ops are not. Your answer doesn't so much give the rationale for the difference (I don't see why there _couldn't_ be something like `requires numeric`) as much as explain the different implementation mechanisms. – Daniel May 14 '12 at 21:13
  • I've been updating the answer. Yes, `equality` and `comparison` are special. Why couldn't there be something for `+`? Well isn't that operator also defined for strings? In some languages for lists and collections? Surely it would be an `addable` constraint and not `numeric`. Many such constraints can be found in a program, so F# provides a 'catch-all' method with static member constraints and the `inline` keyword. – yamen May 14 '12 at 21:16
  • I don't know the answer, but I suspect generic math ops are inlined mostly for performance and the constraints are just a by-product. – Daniel May 14 '12 at 21:27
2

why the difference in generalization?

There is a trade-off between generality and performance. The comparison constraint provides generality for functions like min that can act upon any value of any F# type but in the general case it resorts to virtual dispatch and is many times slower. The + operator provides restricted generality and can act upon any value of any F# type that has been augmented with an overload but does not work in the general case and, therefore, is always very fast because dispatch is never needed.

J D
  • 48,105
  • 13
  • 171
  • 274
1

comparison is a compile-time constraint. So the question remains: why isn't add generalized? As yamen pointed out, generic math ops require inlining, which affects code size and performance—probably not something the compiler should do automatically.

Daniel
  • 47,404
  • 11
  • 101
  • 179
  • Affects code size negatively but performance positively. I don't know if there are other trade-offs. – yamen May 14 '12 at 21:55