Ограничения типа статического члена F # - PullRequest
21 голосов
/ 15 мая 2010

Я пытаюсь определить функцию factorize, которая использует структурные ограничения типа (требуются статические члены Zero, One, + и /), аналогичные Seq.sum, чтобы ее можно было использовать с int, long, bigint, и т.д. Я не могу понять синтаксис правильно, и не могу найти много ресурсов по этому вопросу. Вот что у меня есть, помогите пожалуйста.

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

Ответы [ 3 ]

22 голосов
/ 15 мая 2010

Вот как я это напишу:

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

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

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) []
7 голосов
/ 16 мая 2010

Вдохновленный ответом kvb с использованием NumericLiterals, я был вынужден разработать подход, который позволил бы нам принудительно устанавливать подписи «вменяемого» типа без необходимости добавлять расширенные аннотации типов.

Сначала мы определим некоторые вспомогательные функции и тип оболочки для языковых примитивов:

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
}

Тогда имеем:

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

[ Редактировать : из-за явной ошибки с F # 2.0 / .NET 2.0, factorizen, factorizeL и factorizeI ниже работают значительно медленнее, чем factorizeG при компиляции в режиме Release, но в остальном работают немного быстрее, чем ожидалось - см. вопрос производительности F #: что делает компилятор? ]

Или мы можем сделать еще один шаг вперед (вдохновленный Expert F #, стр.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

Кроме того, вот расширенная версия NumericLiteralG kvb, которая позволяет нам использовать «2G», «-8G» и т. Д. Хотя я не мог понять, как реализовать стратегию запоминания (хотя это должно быть выполнимо для 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 
4 голосов
/ 15 мая 2010

Во-первых, вот тривиальный пример, который показывает, как должен выглядеть синтаксис:

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

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

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

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

[ EDIT : Это на самом деле возможно для некоторых функций (см. Ответ kvb)]

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

...