37 votes

Comment écrire une fonction pour des nombres génériques?

Je suis assez nouveau pour F# et trouver l'inférence de type est vraiment cool. Mais actuellement, il semble qu'il peut aussi conduire à la duplication de code, qui n'est pas une bonne chose. Je veux faire la somme des chiffres d'un nombre comme ceci:

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

crossfoot 123

Ce imprime correctement 6. Mais maintenant, mon numéro d'entrée ne correspond pas int de 32 bits, donc je dois le transformer.

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

crossfoot 123L

Puis, un BigInteger vient à ma rencontre et devinez quoi...

Bien sûr, je pouvais avoir l' bigint version et la fonte des paramètres d'entrée et de sortie les paramètres si nécessaire. Mais d'abord, je suppose à l'aide de BigInteger sur int a certaines performances de pénalités. Deuxième let cf = int (crossfoot (bigint 123)) n'a tout simplement pas lu nice.

N'est-il pas un moyen générique d'écrire cela?

25voto

Daniel Points 29764

La construction de Brian et Stephen réponses, voici un code complet:

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


Mise à JOUR: Réponse Simple

Voici autonome de mise en œuvre, sans l' NumericLiteralG module, et un peu moins restrictive type déduit:

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

Explication

Il y a effectivement deux types de génériques en F#: 1) l'exécution type de polymorphisme, via .NET interfaces/l'héritage, et 2) la compilation des génériques. Au moment de la compilation de génériques sont nécessaires pour accueillir des choses comme générique opérations numériques et quelque chose comme duck-typing (membre explicite des contraintes). Ces fonctionnalités sont intégrées à F# mais non pris en charge dans .NET, donc, par conséquent, doivent être traitées par F# au moment de la compilation.

L'accent circonflexe (^) est utilisé pour différencier résolu statiquement (à la compilation) paramètres de type ordinaire (ce qui d'utiliser une apostrophe). En bref, 'a est traité au moment de l'exécution, ^a au moment de la compilation, raison pour laquelle la fonction doit être marquée inline.

Je n'avais jamais essayé d'écrire quelque chose comme ça avant. Il s'est avéré plus maladroit que ce que j'attendais. Le plus gros problème que je vois à l'écriture générique code numérique en F# est: la création d'une instance d'un générique de nombre autre que zéro ou un. La mise en œuvre d' FromInt32 dans cette réponse pour voir ce que je veux dire. GenericZero et GenericOne sont intégrés, et ils sont mis en œuvre en utilisant des techniques qui ne sont pas disponibles dans le code de l'utilisateur. Dans cette fonction, puisque nous avons seulement besoin d'un petit nombre (10), j'ai créé une séquence de 10 GenericOnes et additionnés entre eux.

Je ne peux pas l'expliquer ainsi pourquoi toutes les annotations de type sont nécessaires, sauf pour dire qu'il apparaît à chaque fois que le compilateur rencontre une opération sur un type générique, il semble penser qu'il est face à un nouveau type. De sorte qu'il finit par déduire certains type bizarre avec dupliqué resitrictions (par exemple, il peut exiger (+) plusieurs fois). Ajouter les annotations de type permet de savoir que nous avons affaire avec le même type long. Le code fonctionne très bien sans eux, mais en ajoutant à leur simplifie la déduit de la signature.

16voto

Stephen Swensen Points 13439

En plus de kvb de la technique à l'aide de Littéraux Numériques (Brian le lien), j'ai eu beaucoup de succès en utilisant une autre technique qui peut donner de meilleurs déduit le type de construction des signatures et peut également être utilisé pour créer précalculées type de fonctions spécifiques pour améliorer les performances ainsi que le contrôle des prises en charge les types numériques (puisque vous voudrez souvent à l'appui de tous les types intégraux, mais pas rationnelle types, par exemple): F# Membre Statique Type de Contraintes.

Suite à la discussion Daniel et moi avons été d'avoir sur le type inféré signatures produites par les différentes techniques, en voici un aperçu:

NumericLiteralG Technique

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 sans ajout d'annotations de type:

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 ajoutant quelques annotations de type:

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)

Enregistrement De Type Technique

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, pas d'annotations nécessaires pour nice déduit de la signature:

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, pas d'annotations, accepte précalculées instances de 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

J'utilise le ci-dessus dans la pratique, car alors je peux faire précalculées type des versions spécifiques qui ne souffrent pas de la performance coût de Générique LanguagePrimitives:

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)

14voto

kvb Points 35490

Depuis la question de savoir comment rendre le type signatures moins poilues lors de l'utilisation de la généralisation de littéraux numériques a venir, je pensais le mettre dans mes deux cents. Le principal problème est que F#'s, les opérateurs peuvent être asymétrique, de sorte que vous pouvez faire des trucs comme System.DateTime.Now + System.TimeSpan.FromHours(1.0), ce qui signifie que F#'s l'inférence de type, ajoute l'intermédiaire des variables de type à chaque fois que des opérations arithmétiques sont effectués.

Dans le cas d'algorithmes numériques, ce potentiel d'asymétrie n'est généralement pas utile et l'explosion qui s'ensuit dans le type de signatures est assez moche (bien que généralement, il n'affecte pas F#, la capacité d'appliquer les fonctions correctement face à béton arguments). Une solution possible à ce problème est de restreindre les types d'opérateurs arithmétiques dans le champ d'application que vous vous souciez. Par exemple, si vous définissez ce module:

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
  ...

ensuite, vous pouvez simplement ouvrir l' SymmetricOps module à chaque fois que vous voulez avoir les opérateurs s'appliquent uniquement à deux arguments du même type. Ainsi, nous pouvons maintenant définir:

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

et

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

et le type inféré est relativement propre

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

tandis que nous continuons d'obtenir le bénéfice d'une belle, lisible à la définition d' crossfoot.

6voto

Brian Points 82719

1voto

cdonlan Points 27

Est crossfoot exactement ce que vous voulez faire, ou est-il simplement en additionnant les chiffres d'un numéro de long?

parce que si vous voulez juste faire la somme des chiffres, puis:

let crossfoot (x:'a) = x.ToString().ToCharArray()
                       |> (Array.fold(fun acc x' -> if x' <> '.' 
                                                    then acc + (int x')
                                                    else acc) 0)

... Et vous avez terminé.

De toute façon, Vous pouvez convertir des trucs à une chaîne, baisse de la virgule, rappelez-vous où la virgule est, l'interpréter comme un int, exécutez crossfoot?

Voici ma solution. Je ne suis pas sûr exactement comment vous le voulez "crossfoot" de travail lorsque vous avez un point décimal ajouté.

Par exemple, voulez-vous: crossfoot(123.1) = 7 ou crossfoot(123.1) = 6.1? (Je suppose que vous voulez le dernier)

De toute façon, le code ne vous permettent de travailler avec des nombres que des génériques.

let crossfoot (n:'a) = // Completely generic input

    let rec crossfoot' (a:int) =       // Standard integer crossfoot
        if a = 0 then 0 
        else a%10 + crossfoot' (a / 10)

    let nstr = n.ToString()

    let nn   = nstr.Split([|'.'|])    // Assuming your main constraint is float/int

    let n',n_ = if nn.Length > 1 then nn.[0],nn.[1] 
                else nn.[0],"0"

    let n'',n_' = crossfoot'(int n'),crossfoot'(int n_)

    match n_' with
    | 0 -> string n''
    | _ -> (string n'')+"."+(string n_')

Si vous avez besoin pour l'entrée des grands entiers ou int64 choses, la façon crossfoot fonctionne, vous pouvez juste diviser le grand nombre en petits morceaux (chaînes de caractères) et de les nourrir dans cette fonction, et les additionner.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X