Первичные факторы в F #

Question

Я пытаюсь выучить F #.
Я написал функцию, которая вычленяет простые числа.

let PrimeFactors x =
  let rec PrimeFactorsRecursive x div list =
     if x % div = 0 then PrimeFactorsRecursive (x/div) div list @ [div]
     elif div > int(System.Math.Sqrt(float(x))) then 
       if x > 1 then list @ [x]
       else list
     else PrimeFactorsRecursive x (div + 1) list
  PrimeFactorsRecursive x 2 []

Теперь я не уверен, что это хорошая функция F # или она больше похожа на "c #, написано на f #".

Есть ли "более" функциональный способ записиэтот код?

Answer 1

Основная проблема в вашем коде заключается в том, что вы используете @ для объединения двух списков.Составление двух списков стоит линейное время, а не постоянное время.

Постоянный способ - добавить новое простое число в начало списка с помощью оператора ::, как показано ниже:

let primeFactors x = 
    let rec fact x div list = 
        if x % div = 0 then
            fact (x/div) div (div::list)
        elif div > int(sqrt (float x)) then
            if x > 1 then x::list
            else list
        else
            fact x (div+1) list
    fact x 2 []

Также let значения привязки обычно следуют за camleStyleименования конверсий.

Answer 2

Еще одним «улучшением», которое еще не упоминалось, является использование трубопровода, чтобы вместо

int(System.Math.Sqrt(float(x)))

у вас есть

(x |> float |> sqrt |> int)

Answer 3

Возможно, вы могли бы использовать защищенные шаблоны, чтобы уменьшить вложенность if-выражения. Кроме того, для меня это выглядит вполне разумным идиоматическим функциональным кодом.