CODEWITHSUNDEEP
genericsf#automatic-generalization
Asik
Asik

Reputation: 22133

Generic functions in F#

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.

Upvotes: 9

Views: 1906

Answers (3)

J D
J D

Reputation: 48687

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.

Upvotes: 2

Daniel
Daniel

Reputation: 47904

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.

Upvotes: 1

yamen
yamen

Reputation: 15618

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.

Upvotes: 7

Related Questions