F# assuming int when actually dealing with int64

Question

Going through Project Euler trying to learn F#, I stumbled upon what appears to be a type inference problem while writing a solution for problem 3.

Here's what I wrote:

let rec findLargestPrimeFactor p n = 
    if n = 1 then p
    else
        if n % p = 0 then findLargestPrimeFactor p (n/p)
        else findLargestPrimeFactor (p+1) n

let result = findLargestPrimeFactor 2 600851475143L

However, the compiler gives me the following error:

error FS0001: This expression was expected to have type    int    but here has type    int64

Since I expect the types used in findLargestPrimeFactor to be inferred from usage, I'm quite surprised to find out the compiler seems to assume that parameter n be an int since in the only call to the function is done with an int64.

Could someone explain to me:

1. why the compiler appears to be confused about types
2. how to work around this limitation

Answer 1

The types in findLargestPrimeFactor are inferred from usage. The F# compiler performs type inference in a top-to-bottom manner, so the types of p and n (the parameters of findLargestPrimeFactor) are inferred from their usage in the function. By the time the compiler sees the let result = ..., the parameter types have already been inferred as int.

The easiest solution is to use the L suffix on all of your constant values, so the types will be inferred as int64:

let rec findLargestPrimeFactor p n = 
    if n = 1L then p
    else
        if n % p = 0L then findLargestPrimeFactor p (n/p)
        else findLargestPrimeFactor (p + 1L) n

let result = findLargestPrimeFactor 2L 600851475143L

If you want a fancier solution, you can use the generic one and zero constants from the LanguagePrimitives module. This allows findLargestPrimeFactor to be generic(-ish) so it can be reused more easily with different numeric types:

open LanguagePrimitives

let rec findLargestPrimeFactor p n = 
    if n = GenericOne then p
    else
        if n % p = GenericZero then findLargestPrimeFactor p (n/p)
        else findLargestPrimeFactor (p + GenericOne) n

(* You can use one of these, but not both at the same time --
   now the types of the _arguments_ are used to infer the types
   of 'p' and 'n'. *)

//let result = findLargestPrimeFactor 2L 600851475143L
let result = findLargestPrimeFactor 2 Int32.MaxValue

Per @kvb's suggestion, here's how you can write this function generically:

open LanguagePrimitives

let inline findLargestPrimeFactor p n =
    let rec findLargestPrimeFactor p n =
        if n = GenericOne then p
        else
            if n % p = GenericZero then findLargestPrimeFactor p (n/p)
            else findLargestPrimeFactor (p + GenericOne) n
    findLargestPrimeFactor p n

(* Now you can call the function with different argument types
   as long as the generic constraints are satisfied. *)
let result = findLargestPrimeFactor 2L 600851475143L
let result' = findLargestPrimeFactor 2 Int32.MaxValue