F#静态成员类型约束

Question

我尝试定义一个函数factorize，它使用结构类型约束（需要静态成员Zero、One、+和/），类似于Seq.sum，以便可以与int、long、bigint等一起使用。我似乎无法得到正确的语法，并且在这个主题上找不到很多资源。这是我目前的代码，请帮忙。

let inline factorize (n:^NUM) =
    ^NUM : (static member get_Zero: unit->(^NUM))
    ^NUM : (static member get_One: unit->(^NUM))
    let rec factorize (n:^NUM) (j:^NUM) (flist: ^NUM list) = 
        if n = ^NUM.One then flist
        elif n % j = ^NUM.Zero then factorize (n/j) (^NUM.One + ^NUM.One) (j::flist)
        else factorize n (j + ^NUM.One) (flist)
    factorize n (^NUM.One + ^NUM.One) []

- Stephen Swensen

Answer 1

这是我的写法：

module NumericLiteralG = begin
  let inline FromZero() = LanguagePrimitives.GenericZero
  let inline FromOne() = LanguagePrimitives.GenericOne
end

let inline factorize n = 
  let rec factorize n j flist =  
    if n = 1G then flist 
    elif n % j = 0G then factorize (n/j) j (j::flist) 
    else factorize n (j + 1G) (flist) 
  factorize n (1G + 1G) [] 

对于factorize函数推断出的类型过于泛化，但函数会按照您所期望的工作。如果您希望强制使用更合理的签名和约束集，可以通过将某些通用表达式添加显式类型来实现：

let inline factorize (n:^a) : ^a list = 
  let (one : ^a) = 1G
  let (zero : ^a) = 0G
  let rec factorize n (j:^a) flist =  
    if n = one then flist 
    elif n % j = zero then factorize (n/j) j (j::flist) 
    else factorize n (j + one) (flist) 
  factorize n (one + one) []

- kvb

---

你说得对 - 这个可以工作 - 对我来说相当惊讶 :-). 我不确定这里发生了什么，因为 factorize 被编译为通用函数。它使用 GetZero 的动态实现（可能类似于使用 NumericAssociations），但我不确定这是如何工作的（没有显式注册自己类型的操作）。如果你理解这是如何工作的，我会非常感兴趣了解细节 :-). - Tomas Petricek

刚刚注意到你在算法的elif情况下添加了不错的优化。 - Stephen Swensen

@Tomas - 生成的通用函数是一个误导 - 如果你实际调用它，几乎肯定会在运行时得到NotSupportedException，我不确定编译器为什么会发出它。相反，在任何调用factorize的地方，编译器都会内联整个定义，包括内部递归函数，使用正确的参数类型进行操作。这有帮助吗？ - kvb

@kvb：啊，我明白了，诀窍在于factorize是尾递归的(!)，这意味着它被翻译成循环并且可以实际内联。这就是让我感到困惑的地方！ - Tomas Petricek

@Tomas - 我认为这与是否尾递归无关（例如在factorize的两个递归调用后添加@ []）。 如果您编写let l = factorize 60，则编译器实际上会生成类似于let l =（fun n-> let rec factorize ... in factorize n ...）60的内容。 您无法内联递归函数，但是可以内联包含内部递归函数的函数，而不会遇到任何概念障碍。 - kvb

@kvb：谢谢，现在我终于明白了！:-) - Tomas Petricek

Answer 2

受kvb使用NumericLiterals的答案的启发，我被驱使着开发一种方法，使我们能够在不添加大量类型注释的情况下强制实现“合理”的类型签名。

首先，我们定义一些辅助函数和语言原语的包装器类型：

let inline zero_of (target:'a) : 'a = LanguagePrimitives.GenericZero<'a>
let inline one_of (target:'a) : 'a = LanguagePrimitives.GenericOne<'a>
let inline two_of (target:'a) : 'a = one_of(target) + one_of(target)
let inline three_of (target:'a) : 'a = two_of(target) + one_of(target)
let inline negone_of (target:'a) : 'a = zero_of(target) - one_of(target)

let inline any_of (target:'a) (x:int) : 'a =
    let one:'a = one_of target
    let zero:'a = zero_of target
    let xu = if x > 0 then 1 else -1
    let gu:'a = if x > 0 then one else zero-one

    let rec get i g = 
        if i = x then g
        else get (i+xu) (g+gu)
    get 0 zero 

type G<'a> = {
    negone:'a
    zero:'a
    one:'a
    two:'a
    three:'a
    any: int -> 'a
}    

let inline G_of (target:'a) : (G<'a>) = {
    zero = zero_of target
    one = one_of target
    two = two_of target
    three = three_of target
    negone = negone_of target
    any = any_of target
}

然后我们有：

let inline factorizeG n = 
    let g = G_of n
    let rec factorize n j flist =  
        if n = g.one then flist 
        elif n % j = g.zero then factorize (n/j) j (j::flist) 
        else factorize n (j + g.one) (flist) 
    factorize n g.two []

[编辑：由于F# 2.0/.NET 2.0存在明显的bug，因此在发布模式下编译时，factorizen、factorizeL和factorizeI的运行速度比factorizeG慢得多，但在其他情况下，它们的运行速度略快，如预期所述--请参见F# performance question: what is the compiler doing?]

或者我们可以进一步推进几步（受Expert F#，第110页的启发）：

let inline factorize (g:G<'a>) n =   //'
    let rec factorize n j flist =  
        if n = g.one then flist 
        elif n % j = g.zero then factorize (n/j) j (j::flist) 
        else factorize n (j + g.one) (flist) 
    factorize n g.two []

//identical to our earlier factorizeG
let inline factorizeG n = factorize (G_of n) n

let gn = G_of 1  //int32
let gL = G_of 1L //int64
let gI = G_of 1I //bigint

//allow us to limit to only integral numeric types
//and to reap performance gain by using pre-computed instances of G
let factorizen = factorize gn
let factorizeL = factorize gL
let factorizeI = factorize gI

此外，这是kvb的NumericLiteralG的扩展版本，允许我们使用"2G"，"-8G"等。虽然我无法想出如何实现记忆化策略（尽管对于G.any来说应该是可行的）。

module NumericLiteralG = 
    let inline FromZero() = LanguagePrimitives.GenericZero
    let inline FromOne() = LanguagePrimitives.GenericOne
    let inline FromInt32(n:int):'a =
        let one:'a = FromOne()
        let zero:'a = FromZero()
        let nu = if n > 0 then 1 else -1
        let gu:'a = if n > 0 then one else zero-one

        let rec get i g = 
            if i = n then g
            else get (i+nu) (g+gu)
        get 0 zero 

- Stephen Swensen

Answer 3

首先，这里有一个简单的例子展示了语法应该是怎样的：

let inline zero< ^NUM when ^NUM : (static member get_Zero: unit-> ^NUM)> 
    (n:^NUM) = 
  (^NUM : (static member get_Zero : unit -> ^NUM) ())

在某些情况下，您不需要明确编写约束条件（如果您编写了上述内容，F#编译器实际上会警告您），因为某些静态成员对编译器是众所周知的，并且存在用于使用它们的标准函数。因此，您可以使用该函数，编译器将推断约束条件：

let inline zero (n:^T) = 
  LanguagePrimitives.GenericZero< ^T > 

很遗憾，这并不能帮助你，因为递归函数不能声明为inline（因为编译器不知道函数会被调用多少次，所以无法在编译时内联函数），所以静态约束可能不足以解决你的问题。

[编辑：对于某些函数，实际上是可以的（请参见kvb的答案）]

我认为你需要使用NumericAssociations，这已经在这个问题中讨论过了（这些在运行时处理，所以速度较慢 - 但用于实现例如F#矩阵类型 - 矩阵可以缓存动态获取的信息，因此效率还是比较高的）。

- Tomas Petricek