6

通过Project Euler尝试学习 F#，我在为问题 3编写解决方案时偶然发现了一个类型推断问题。

这是我写的：

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

但是，编译器给了我以下错误：

错误 FS0001：此表达式应为 int 类型，但此处为 int64 类型

由于我希望 in 中使用的类型findLargestPrimeFactor是从用法中推断出来的，我很惊讶地发现编译器似乎假定参数n是一个 int，因为对函数的唯一调用是使用 int64 完成的。

有人可以向我解释一下：

  1. 为什么编译器似乎对类型感到困惑
  2. 如何解决此限制
4

1 回答 1

11

中的类型findLargestPrimeFactor是根据使用情况推断的。F# 编译器以自上而下的方式执行类型推断，因此p和n（的参数findLargestPrimeFactor）的类型是根据它们在函数中的用法推断出来的。当编译器看到 时let result = ...，参数类型已经被推断为int。

最简单的解决方案是在所有常量值上使用L后缀，因此类型将被推断为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

如果您想要一个更好的解决方案，您可以使用LanguagePrimitives模块中的通用 1 和 0 常量。这允许findLargestPrimeFactor通用（-ish），因此可以更轻松地使用不同的数字类型重用它：

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

根据@kvb 的建议，以下是一般编写此函数的方法：

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
于 2013-02-21T17:41:05.270 回答