如何编写通用数字的函数？

Question

我对F#很陌生,发现类型推断确实很酷.但目前似乎它也可能导致代码重复,这不是一件很酷的事情.我想总结一个这样的数字的数字:

let rec crossfoot n =
  if n = 0 then 0
  else n % 10 + crossfoot (n / 10)

crossfoot 123

这正确打印6.但是现在我的输入数字不适合32位,所以我必须将其转换为.

let rec crossfoot n =
  if n = 0L then 0L
  else n % 10L + crossfoot (n / 10L)

crossfoot 123L

然后,BigInteger我来了,猜猜是什么......

当然,我只能提供bigint版本和转换输入参数,并根据需要输出参数.但首先我假设使用BigInteger过度int有一些性能惩罚.第二个let cf = int (crossfoot (bigint 123))不好看.

写这个没有通用的方法吗？

Answer 1

在Brian和Stephen的答案的基础上,这里有一些完整的代码:

module NumericLiteralG = 
    let inline FromZero() = LanguagePrimitives.GenericZero
    let inline FromOne() = LanguagePrimitives.GenericOne
    let inline FromInt32 (n:int) =
        let one : ^a = FromOne()
        let zero : ^a = FromZero()
        let n_incr = if n > 0 then 1 else -1
        let g_incr = if n > 0 then one else (zero - one)
        let rec loop i g = 
            if i = n then g
            else loop (i + n_incr) (g + g_incr)
        loop 0 zero 

let inline crossfoot (n:^a) : ^a =
    let (zero:^a) = 0G
    let (ten:^a) = 10G
    let rec compute (n:^a) =
        if n = zero then zero
        else ((n % ten):^a) + compute (n / ten)
    compute n

crossfoot 123
crossfoot 123I
crossfoot 123L

更新:简单的答案

这是一个独立的实现,没有NumericLiteralG模块,限制性稍强的推断类型:

let inline crossfoot (n:^a) : ^a =
    let zero:^a = LanguagePrimitives.GenericZero
    let ten:^a = (Seq.init 10 (fun _ -> LanguagePrimitives.GenericOne)) |> Seq.sum
    let rec compute (n:^a) =
        if n = zero then zero
        else ((n % ten):^a) + compute (n / ten)
    compute n

说明

F#中实际上有两种类型的泛型:1)运行类型多态,通过.NET接口/继承,以及2)编译时泛型.需要编译时泛型来容纳诸如泛型数字操作之类的东西以及诸如鸭子类型(显式成员约束)之类的东西.这些功能是F#的组成部分,但在.NET中不受支持,因此必须在编译时由F#处理.

caret(^)用于区分静态解析(编译时)类型参数与普通类型参数(使用撇号).简而言之,'a在运行时,^a在编译时处理 - 这就是必须标记函数的原因inline.

我之前从未尝试过写过类似的东西.结果比我想象的更笨拙.我在F#中编写通用数字代码的最大障碍是:创建一个非零或一个通用数字的实例.见实施FromInt32的这个答案,看看我的意思.GenericZero并且GenericOne是内置的,它们是使用用户代码中没有的技术实现的.在这个函数中,由于我们只需要一个小数(10),我创建了一个10 GenericOne秒的序列并将它们相加.

我不能解释为什么需要所有类型注释,除了说每次编译器遇到泛型类型的操作时它似乎认为它正在处理一个新类型.因此它最终会推断出一些具有重复重复的奇怪类型(例如,它可能需要(+)多次).添加类型注释让它知道我们在整个处理相同的类型.没有它们的代码工作正常,但添加它们简化了推断的签名.

Answer 2

除了使用Numeric Literals(Brian的链接)的kvb技术之外,我使用不同的技术获得了很多成功,这种技术可以产生更好的推断结构类型签名,并且还可以用于创建预先计算的类型特定函数以获得更好的性能作为对受支持的数字类型的控制(因为您通常希望支持所有整数类型,但不支持有理类型):F#静态成员类型约束.

继续讨论Daniel和我一直在讨论由不同技术产生的推断类型签名,这里是一个概述:

NumericLiteralG技术

module NumericLiteralG = 
    let inline FromZero() = LanguagePrimitives.GenericZero
    let inline FromOne() = LanguagePrimitives.GenericOne
    let inline FromInt32 (n:int) =
        let one = FromOne()
        let zero = FromZero()
        let n_incr = if n > 0 then 1 else -1
        let g_incr = if n > 0 then one else (zero - one)
        let rec loop i g = 
            if i = n then g
            else loop (i + n_incr) (g + g_incr)
        loop 0 zero 

没有添加任何类型注释的Crossfoot:

let inline crossfoot1 n =
    let rec compute n =
        if n = 0G then 0G
        else n % 10G + compute (n / 10G)
    compute n

val inline crossfoot1 :
   ^a ->  ^e
    when ( ^a or  ^b) : (static member ( % ) :  ^a *  ^b ->  ^d) and
          ^a : (static member get_Zero : ->  ^a) and
         ( ^a or  ^f) : (static member ( / ) :  ^a *  ^f ->  ^a) and
          ^a : equality and  ^b : (static member get_Zero : ->  ^b) and
         ( ^b or  ^c) : (static member ( - ) :  ^b *  ^c ->  ^c) and
         ( ^b or  ^c) : (static member ( + ) :  ^b *  ^c ->  ^b) and
          ^c : (static member get_One : ->  ^c) and
         ( ^d or  ^e) : (static member ( + ) :  ^d *  ^e ->  ^e) and
          ^e : (static member get_Zero : ->  ^e) and
          ^f : (static member get_Zero : ->  ^f) and
         ( ^f or  ^g) : (static member ( - ) :  ^f *  ^g ->  ^g) and
         ( ^f or  ^g) : (static member ( + ) :  ^f *  ^g ->  ^f) and
          ^g : (static member get_One : ->  ^g)

Crossfoot添加一些类型注释:

let inline crossfoot2 (n:^a) : ^a =
    let (zero:^a) = 0G
    let (ten:^a) = 10G
    let rec compute (n:^a) =
        if n = zero then zero
        else ((n % ten):^a) + compute (n / ten)
    compute n

val inline crossfoot2 :
   ^a ->  ^a
    when  ^a : (static member get_Zero : ->  ^a) and
         ( ^a or  ^a0) : (static member ( - ) :  ^a *  ^a0 ->  ^a0) and
         ( ^a or  ^a0) : (static member ( + ) :  ^a *  ^a0 ->  ^a) and
          ^a : equality and  ^a : (static member ( + ) :  ^a *  ^a ->  ^a) and
          ^a : (static member ( % ) :  ^a *  ^a ->  ^a) and
          ^a : (static member ( / ) :  ^a *  ^a ->  ^a) and
          ^a0 : (static member get_One : ->  ^a0)

记录类型技术

module LP =
    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
    }

open LP

Crossfoot,没有明确推断签名所需的注释:

let inline crossfoot3 n =
    let g = G_of n
    let ten = g.any 10
    let rec compute n =
        if n = g.zero then g.zero
        else n % ten + compute (n / ten)
    compute n

val inline crossfoot3 :
   ^a ->  ^a
    when  ^a : (static member ( % ) :  ^a *  ^a ->  ^b) and
         ( ^b or  ^a) : (static member ( + ) :  ^b *  ^a ->  ^a) and
          ^a : (static member get_Zero : ->  ^a) and
          ^a : (static member get_One : ->  ^a) and
          ^a : (static member ( + ) :  ^a *  ^a ->  ^a) and
          ^a : (static member ( - ) :  ^a *  ^a ->  ^a) and  ^a : equality and
          ^a : (static member ( / ) :  ^a *  ^a ->  ^a)

Crossfoot,没有注释,接受G的预先计算的实例:

let inline crossfootG g ten n =
    let rec compute n =
        if n = g.zero then g.zero
        else n % ten + compute (n / ten)
    compute n

val inline crossfootG :
  G< ^a> ->  ^b ->  ^a ->  ^a
    when ( ^a or  ^b) : (static member ( % ) :  ^a *  ^b ->  ^c) and
         ( ^c or  ^a) : (static member ( + ) :  ^c *  ^a ->  ^a) and
         ( ^a or  ^b) : (static member ( / ) :  ^a *  ^b ->  ^a) and
          ^a : equality

我在实践中使用上述内容,因为那时我可以制作预先计算的类型特定版本,而不会受到通用语言原理的性能成本的影响:

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

let gD = G_of 1.0  //double
let gS = G_of 1.0f //single
let gM = G_of 1.0m //decimal

let crossfootn = crossfootG gn (gn.any 10)
let crossfootL = crossfootG gL (gL.any 10)
let crossfootI = crossfootG gI (gI.any 10)
let crossfootD = crossfootG gD (gD.any 10)
let crossfootS = crossfootG gS (gS.any 10)
let crossfootM = crossfootG gM (gM.any 10)

Answer 3

由于在使用广义数字文字时如何使类型签名不那么毛茸茸的问题已经出现了,我想我会投入两分钱.主要问题是F#的运算符可以是非对称的,这样你就可以做类似的事情System.DateTime.Now + System.TimeSpan.FromHours(1.0),这意味着只要执行算术运算,F#的类型推断就会增加中间类型变量.

在数值算法的情况下,这种潜在的不对称性通常不常用,并且类型签名中的结果爆炸非常难看(尽管它通常不会影响F#在给定具体参数时正确应用函数的能力).此问题的一个可能解决方案是在您关注的范围内限制算术运算符的类型.例如,如果您定义此模块:

module SymmetricOps =
  let inline (+) (x:'a) (y:'a) : 'a = x + y
  let inline (-) (x:'a) (y:'a) : 'a = x - y
  let inline (*) (x:'a) (y:'a) : 'a = x * y
  let inline (/) (x:'a) (y:'a) : 'a = x / y
  let inline (%) (x:'a) (y:'a) : 'a = x % y
  ...

那么SymmetricOps只要你想让运算符只应用于同一类型的两个参数,你就可以打开模块.所以现在我们可以定义:

module NumericLiteralG = 
  open SymmetricOps
  let inline FromZero() = LanguagePrimitives.GenericZero
  let inline FromOne() = LanguagePrimitives.GenericOne
  let inline FromInt32 (n:int) =
      let one = FromOne()
      let zero = FromZero()
      let n_incr = if n > 0 then 1 else -1
      let g_incr = if n > 0 then one else (zero - one)
      let rec loop i g = 
          if i = n then g
          else loop (i + n_incr) (g + g_incr)
      loop 0 zero

和

open SymmetricOps
let inline crossfoot x =
  let rec compute n =
      if n = 0G then 0G
      else n % 10G + compute (n / 10G)
  compute x

而推断的类型是相对干净的

val inline crossfoot :
   ^a ->  ^a
    when  ^a : (static member ( - ) :  ^a *  ^a ->  ^a) and
          ^a : (static member get_One : ->  ^a) and
          ^a : (static member ( % ) :  ^a *  ^a ->  ^a) and
          ^a : (static member get_Zero : ->  ^a) and
          ^a : (static member ( + ) :  ^a *  ^a ->  ^a) and
          ^a : (static member ( / ) :  ^a *  ^a ->  ^a) and  ^a : equality

虽然我们仍然可以获得一个漂亮,可读的定义crossfoot.