generics - usando - variable de tipo genérico

F#Restricciones del tipo de miembro estático

Question

Estoy tratando de definir una función, factorizar, que utiliza restricciones de tipo estructural (requiere miembros estáticos cero, uno, + y /) similar a Seq.sum para que se pueda usar con int, long, bigint, etc. Parece que no puede obtener la sintaxis correcta y no puede encontrar muchos recursos sobre el tema. Esto es lo que tengo, por favor ayuda.

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) []

Answer 1

Así es como lo escribiría:

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) [] 

El tipo inferido para factorizar aquí es demasiado general, pero la función funcionará como es de esperar. Puede forzar una firma más sana y un conjunto de restricciones si lo desea agregando tipos explícitos a algunas de las expresiones genéricas:

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) []

Answer 2

En primer lugar, aquí hay un ejemplo trivial que muestra cómo debería ser la sintaxis:

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

En algunos casos, no es necesario que escriba las restricciones explícitamente (el compilador F # en realidad lo advertirá si escribe lo anterior), porque algunos miembros estáticos son bien conocidos por el compilador y existen funciones estándar para usarlos. . Entonces, puedes usar la función y el compilador inferirá la restricción:

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

Desafortunadamente, esto realmente no lo ayuda, porque las funciones recursivas no se pueden declarar como en inline (por razones obvias: el compilador no puede alinear la función en tiempo de compilación, porque no sabe cuántas veces), por lo que las restricciones estáticas probablemente no lo suficientemente poderoso para su problema.

[ EDITAR : Esto es posible para algunas funciones (ver la respuesta de kvb)]

Creo que necesitarás NumericAssociations , que en este momento se discutieron en esta pregunta (estas se procesan en tiempo de ejecución, por lo que son más lentas, pero se usan para implementar, por ejemplo, el tipo de matriz F #; la matriz puede almacenar en caché la información obtenida dinámicamente; es razonablemente eficiente).

Answer 3

Inspirado por la respuesta de kvb usando NumericLiterals, me vi impulsado a desarrollar un enfoque que nos permitiera forzar firmas de tipo "cuerdas" sin tener que agregar anotaciones de tipo extensas.

Primero definimos algunas funciones auxiliares y el tipo de envoltorio para las primitivas del lenguaje:

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
}

Entonces nosotros tenemos:

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 []

[ Editar : debido a un error aparente con F # 2.0 / .NET 2.0, factorizen, factorizeL y factorizeI a continuación se ejecuta significativamente más lento que factorizeG cuando se compila en modo Release, pero se ejecuta ligeramente más rápido como se esperaba - ver F # pregunta de rendimiento: ¿qué es? el compilador? ]

O podemos dar un paso más (inspirado en Expert F #, p.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

Además, aquí hay una versión extendida de kvb''s NumericLiteralG que nos permite usar "2G", "-8G", etc. Aunque no pude encontrar la manera de implementar una estrategia de memorización (aunque eso debería ser factible para 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