Как написать функцию для общих чисел? - PullRequest
Новая
       68

Как написать функцию для общих чисел?

37 голосов
/ 19 января 2011

Я довольно новичок в 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)) просто не читает хорошо.

Нет ли общего способа написать это?

Ответы [ 5 ]

25 голосов
/ 19 января 2011

Основываясь на ответах Брайана и Стивена, вот несколько полных кодов: 

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) run-typeполиморфизм через .NET-интерфейсы / наследование, и 2) обобщение времени компиляции.Обобщения во время компиляции необходимы для приспособления к таким вещам, как универсальные числовые операции и что-то вроде утки ( явные ограничения членов ).Эти функции являются неотъемлемой частью F #, но не поддерживаются в .NET, поэтому должны обрабатываться F # во время компиляции.

Символ каретки (^) используется для дифференциации статически разрешенного (время компиляции)) введите параметры из обычных (которые используют апостроф).Короче говоря, 'a обрабатывается во время выполнения, ^a во время компиляции - именно поэтому функция должна быть помечена inline.

Я никогда раньше не пытался написать что-то подобное.Получилось неуклюже, чем я ожидал.Самое большое препятствие, которое я вижу при написании универсального числового кода на F #, - это создание экземпляра универсального числа, отличного от нуля или единицы.Посмотрите реализацию FromInt32 в этого ответа , чтобы понять, что я имею в виду.GenericZero и GenericOne являются встроенными и реализованы с использованием методов, недоступных в пользовательском коде.В этой функции, поскольку нам нужно было только небольшое число (10), я создал последовательность из 10 GenericOne с и суммировал их.

Я также не могу объяснить, зачем нужны все аннотации типов,кроме того, что он появляется каждый раз, когда компилятор встречает операцию с универсальным типом, кажется, что он имеет дело с новым типом.Таким образом, это приводит к выводу некоторого странного типа с дублирующимися ограничениями (например, может потребоваться (+) несколько раз).Добавление аннотаций типов позволяет понять, что мы имеем дело с одним и тем же типом.Код работает без них, но их добавление упрощает выводимую подпись.

16 голосов
/ 19 января 2011

В дополнение к методике kvb с использованием числовых литералов (ссылка Брайана), я добился большого успеха, используя другую технику, которая может давать более качественные сигнатуры структурного типа и может также использоваться для создания предварительно вычисленных функций, специфичных для типа, для лучшего производительность, а также контроль над поддерживаемыми числовыми типами (поскольку вам часто требуется поддерживать все целочисленные типы, но не рациональные типы, например): F # Статические ограничения на типы элементов .

В продолжение дискуссии с Дэниелом и мной о логических выводах типа, полученных с помощью различных методов, вот обзор:

Метод 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

Я использую вышеупомянутое на практике, с тех пор я могу делать версии для конкретных предварительно вычисленных типов, которые не страдают от затрат производительности Generic 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)
14 голосов
/ 19 января 2011

Поскольку встал вопрос о том, как сделать сигнатуры типов менее волосатыми при использовании обобщенных числовых литералов, я решил поставить свои два цента.Основная проблема заключается в том, что операторы 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.

2 голосов
/ 14 апреля 2014

Я наткнулся на эту тему, когда искал решение, и публикую свой ответ, потому что я нашел способ выразить общую цифру без менее оптимальной реализации построения числа вручную.

open System.Numerics
// optional
open MathNet.Numerics

module NumericLiteralG = 
    type GenericNumber = GenericNumber with
        static member instance (GenericNumber, x:int32, _:int8) = fun () -> int8 x
        static member instance (GenericNumber, x:int32, _:uint8) = fun () -> uint8 x
        static member instance (GenericNumber, x:int32, _:int16) = fun () -> int16 x
        static member instance (GenericNumber, x:int32, _:uint16) = fun () -> uint16 x
        static member instance (GenericNumber, x:int32, _:int32) = fun () -> x
        static member instance (GenericNumber, x:int32, _:uint32) = fun () -> uint32 x
        static member instance (GenericNumber, x:int32, _:int64) = fun () -> int64 x
        static member instance (GenericNumber, x:int32, _:uint64) = fun () -> uint64 x
        static member instance (GenericNumber, x:int32, _:float32) = fun () -> float32 x
        static member instance (GenericNumber, x:int32, _:float) = fun () -> float x
        static member instance (GenericNumber, x:int32, _:bigint) = fun () -> bigint x
        static member instance (GenericNumber, x:int32, _:decimal) = fun () -> decimal x
        static member instance (GenericNumber, x:int32, _:Complex) = fun () -> Complex.op_Implicit x
        static member instance (GenericNumber, x:int64, _:int64) = fun () -> int64 x
        static member instance (GenericNumber, x:int64, _:uint64) = fun () -> uint64 x
        static member instance (GenericNumber, x:int64, _:float32) = fun () -> float32 x
        static member instance (GenericNumber, x:int64, _:float) = fun () -> float x
        static member instance (GenericNumber, x:int64, _:bigint) = fun () -> bigint x
        static member instance (GenericNumber, x:int64, _:decimal) = fun () -> decimal x
        static member instance (GenericNumber, x:int64, _:Complex) = fun () -> Complex.op_Implicit x
        static member instance (GenericNumber, x:string, _:float32) = fun () -> float32 x
        static member instance (GenericNumber, x:string, _:float) = fun () -> float x
        static member instance (GenericNumber, x:string, _:bigint) = fun () -> bigint.Parse x
        static member instance (GenericNumber, x:string, _:decimal) = fun () -> decimal x
        static member instance (GenericNumber, x:string, _:Complex) = fun () -> Complex(float x, 0.0)
        // MathNet.Numerics
        static member instance (GenericNumber, x:int32, _:Complex32) = fun () -> Complex32.op_Implicit x
        static member instance (GenericNumber, x:int32, _:bignum) = fun () -> bignum.FromInt x
        static member instance (GenericNumber, x:int64, _:Complex32) = fun () -> Complex32.op_Implicit x
        static member instance (GenericNumber, x:int64, _:bignum) = fun () -> bignum.FromBigInt (bigint x)
        static member instance (GenericNumber, x:string, _:Complex32) = fun () -> Complex32(float32 x, 0.0f)
        static member instance (GenericNumber, x:string, _:bignum) = fun () -> bignum.FromBigInt (bigint.Parse x)

    let inline genericNumber num = Inline.instance (GenericNumber, num) ()

    let inline FromZero () = LanguagePrimitives.GenericZero
    let inline FromOne () = LanguagePrimitives.GenericOne
    let inline FromInt32 n = genericNumber n
    let inline FromInt64 n = genericNumber n
    let inline FromString n = genericNumber n

эта реализация выполняется без сложной итерации во время приведения.Он использует FsControl для модуля Instance.

http://www.fssnip.net/mv

1 голос
/ 19 августа 2012

Является ли кроссфут именно тем, что вы хотите сделать, или это просто суммирование цифр длинного числа?

потому что, если вы просто хотите сложить цифры, то: 

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

... И все готово.

В любом случае, Можете ли вы преобразовать материал в строку, удалить десятичную точку, запомнить, где находится десятичная точка, интерпретировать ее как int, запустить crossfoot?

Вот мое решение. Я не совсем уверен, как именно вы хотите, чтобы «кроссфут» работал, если у вас добавлена ​​десятичная точка.

Например, вы хотите: crossfoot(123.1) = 7 или crossfoot(123.1) = 6.1? (Я предполагаю, что вы хотите последнее)

В любом случае, код позволяет вам работать с числами в качестве обобщенных. 

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_')

Если вам нужно ввести большие целые числа или вещи типа int64, как работает кроссфут, вы можете просто разбить большое число на куски (строки) размером в куски, передать их в эту функцию и сложить вместе.

...