Функциональное программирование становится легче и более автоматическим с практикой, так что не переживайте, если вы не поняли его с первой попытки.
Имея это в виду, давайте возьмем ваш пример кода:
let rec findNextPrimeFactor(number:int64, prime:int64):int64 =
if number = 1L then prime else
//************* No variable
(fun p -> findNextPrimeFactor(number / p, p))(nextPrime(prime))
//*************
//************* Variable
let p = nextPrime(prime)
findNextPrimeFactor(number / p, p)
//*************
Ваша no variable версия просто странная, не используйте ее. Мне нравится ваша версия с явной привязкой let.
Другой способ написать это будет:
nextPrime(prime) |> fun p -> findNextPrimeFactor(number / p, p)
Это хорошо и иногда полезно написать это так, но все же выглядит немного странно. В большинстве случаев мы используем |> для каррирования значений без необходимости именовать наши переменные (в стиле "pointfree"). Постарайтесь предвидеть, как будет использоваться ваша функция, и, если возможно, переписать ее, чтобы вы могли использовать ее с оператором канала без явных объявленных переменных. Например:
let rec findNextPrimeFactor number prime =
match number / prime with
| 1L -> prime
| number' -> nextPrime(prime) |> findNextPrimeFactor number'
Аргументов больше нет:)
Хорошо, теперь, когда это у нас в стороне, давайте посмотрим на вашу isPrime функцию:
let isPrime(n:int64) =
let rec check(i:int64) =
i > n / 2L or (n % i <> 0L && check(i + 1L))
check(2L)
Вы, наверное, слышали, чтобы использовать рекурсию вместо циклов, и это правильно. Но, где это возможно, вы должны абстрагироваться от рекурсии с помощью сгибов, карт или функций более высокого порядка. Для этого есть две причины:
немного более читабельно, а
неправильно записанная рекурсия приведет к переполнению стека. Например, ваша функция не является хвостовой рекурсией, поэтому она будет взорвана при больших значениях n.
Я бы переписал isPrime так:
let isPrime n = seq { 2L .. n / 2L } |> Seq.exists (fun i -> n % i = 0L) |> not
В большинстве случаев, если вы можете абстрагироваться от явного зацикливания, тогда вы просто применяете преобразования к входной последовательности, пока не получите результаты:
let maxFactor n =
seq { 2L .. n - 1L } // test inputs
|> Seq.filter isPrime // primes
|> Seq.filter (fun x -> n % x = 0L) // factors
|> Seq.max // result
У нас даже нет промежуточных переменных в этой версии. Прохлада!
Мой второй приоритет - мне бы хотелось
Быть быстрым и эффективным.
В большинстве случаев F # будет довольно сравнимым с C # с точки зрения скорости или "достаточно быстрым". Если вы обнаружите, что выполнение вашего кода занимает много времени, это, вероятно, означает, что вы используете неправильную структуру данных или неверный алгоритм. Для конкретного примера прочитайте комментарии к этому вопросу .
Итак, код, который я написал, «элегантен» в том смысле, что он лаконичен, дает правильные результаты и не использует никаких хитростей. К сожалению, это не очень быстро. Для начала:
он использует пробное деление для создания последовательности простых чисел, когда Сито Эратосфена будет намного быстрее. [Редактировать: я написал несколько наивную версию этого сита, которая не работала для чисел, больших, чем Int32.MaxValue, поэтому я удалил код.]
прочитайте статью в Википедии о функции подсчета простых чисел , она даст вам советы по вычислению первых n простых чисел, а также по оценке верхней и нижней границ для простого числа nth .
[Edit: я включил некоторый код с несколько наивной реализацией сита из эратосфена. Он работает только для входных данных, меньших int32.MaxValue, поэтому, вероятно, он не подходит для проекта euler.]