Как написать функцию для общих чисел?
Я довольно новичок в 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)) просто не читает приятно.
Разве нет общего способа написать это?
6 ответов
Основываясь на ответах Брайана и Стивена, вот несколько полных кодов:
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# во время компиляции.
Каретка (^) используется, чтобы отличать статически разрешенные (во время компиляции) параметры типа от обычных (которые используют апостроф). Короче, 'a обрабатывается во время выполнения, ^a во время компиляции - поэтому функция должна быть помечена inline,
Я никогда не пытался написать что-то подобное раньше. Получилось неуклюже, чем я ожидал. Самое большое препятствие, которое я вижу при написании универсального числового кода на F#, - это создание экземпляра универсального числа, отличного от нуля или единицы. Смотрите реализацию FromInt32 в этом ответе, чтобы понять, что я имею в виду. GenericZero а также GenericOne встроены, и они реализованы с использованием методов, которые недоступны в коде пользователя. В этой функции, поскольку нам нужно было только небольшое число (10), я создал последовательность из 10 GenericOneи подвёл их.
Я также не могу объяснить, зачем нужны все аннотации типов, за исключением того, что он появляется каждый раз, когда компилятор сталкивается с операцией над универсальным типом, кажется, что он имеет дело с новым типом. Таким образом, в конечном итоге выводится какой-то странный тип с дублирующимися ограничениями (например, может потребоваться (+) многократно). Добавление аннотаций типов позволяет понять, что мы имеем дело с одним и тем же типом. Код работает без них, но их добавление упрощает предполагаемую подпись.
В дополнение к методике 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)
Поскольку встал вопрос о том, как сделать сигнатуры типов менее волосатыми при использовании обобщенных числовых литералов, я решил поставить свои два цента. Основная проблема в том, что операторы 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,
Я наткнулся на эту тему, когда искал решение, и я публикую свой ответ, потому что я нашел способ выразить общую цифру без менее оптимальной реализации построения числа вручную.
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.
Является ли кроссфут именно тем, что вы хотите сделать, или это просто суммирование цифр длинного числа?
потому что если вы просто хотите сложить цифры, то:
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, как работает кроссфут, вы можете просто разбить большое число на куски (строки) размером в куски, передать их в эту функцию и сложить их вместе.