Как изменить код F #, чтобы не использовать изменяемый аккумулятор? - PullRequest
Новая
       22

Как изменить код F #, чтобы не использовать изменяемый аккумулятор?

2 голосов
/ 15 июля 2010

Следующий код F # дает правильный ответ на вопрос Project Euler # 7 : 

let isPrime num =
    let upperDivisor = int32(sqrt(float num))   // Is there a better way?
    let rec evaluateModulo a =
        if a = 1 then
            true
        else
            match num % a with
            | 0 -> false
            | _ -> evaluateModulo (a - 1)
    evaluateModulo upperDivisor

let mutable accumulator = 1   // Would like to avoid mutable values.
let mutable number = 2        // ""

while (accumulator <= 10001) do
    if (isPrime number) then
        accumulator <- accumulator + 1
    number <- number + 1

printfn "The 10001st prime number is %i." (number - 1)  // Feels kludgy.
printfn ""
printfn "Hit any key to continue."
System.Console.ReadKey() |> ignore
  1. Я бы хотел избежать значений mutable и аккумулятора и number . Я также хотел бы преобразовать цикл while в хвостовую рекурсивную функцию. Любые советы?
  2. Любые идеи о том, как удалить (число - 1) кладжа, которая отображает результат?
  3. Какие-либо общие замечания по поводу этого кода или предложения по его улучшению?

Ответы [ 3 ]

3 голосов
/ 15 июля 2010

Петли хороши, но более идиоматично абстрагировать петли как можно больше.

let isPrime num =
    let upperDivisor = int32(sqrt(float num))
    match num with
    | 0 | 1 -> false
    | 2 -> true
    | n -> seq { 2 .. upperDivisor } |> Seq.forall (fun x -> num % x <> 0)

let primes = Seq.initInfinite id |> Seq.filter isPrime
let nthPrime n = Seq.nth n primes

printfn "The 10001st prime number is %i." (nthPrime 10001)
printfn ""
printfn "Hit any key to continue."
System.Console.ReadKey() |> ignore

Последовательности - ваш друг:)

1 голос
/ 15 июля 2010

Вы можете сослаться на мой F # для Project Euler Wiki :

Я получил эту первую версию: 

let isPrime n =
    if n=1 then false
    else
        let m = int(sqrt (float(n)))
        let mutable p = true
        for i in 2..m do
            if n%i =0 then p <- false
                           // ~~ I want to break here!
        p

let rec nextPrime n =
    if isPrime n then n
    else nextPrime (n+1)

let problem7 =
    let mutable result = nextPrime 2
    for i in 2..10001 do
        result <- nextPrime (result+1)
    result

В этой версии, хотя выглядит лучше, но яеще не рано разрывать цикл, когда число не простое.В модуле Seq методы Существуют и Форалл поддерживают раннюю остановку: 

let isPrime n =
    if n<=1 then false
    else
        let m = int(sqrt (float(n)))
        {2..m} |> Seq.exists (fun i->n%i=0) |> not
        // or equivalently :
        // {2..m} |> Seq.forall (fun i->n%i<>0)

Обратите внимание, что в этой версии isPrime функция наконец-то математически корректна, проверяя числа ниже 2.

Или вы можете использоватьхвостовая рекурсивная функция для выполнения цикла while: 

let isPrime n = 
    let m = int(sqrt (float(n)))
    let rec loop i =
        if i>m then true
        else 
            if n%i = 0 then false
            else loop (i+1)
    loop 2

Более функциональная версия задачи7 - использовать Seq.unfold для генерации бесконечной простой последовательности и взять n-й элемент этой последовательности: 

let problem7b =
    let primes =
        2 |> Seq.unfold (fun p ->
            let next = nextPrime (p+1) in
            Some( p, next ) )
    Seq.nth 10000 primes
0 голосов
/ 15 июля 2010

Вот мое решение, которое использует шаблон с хвостовой рекурсивной петлей, который всегда позволяет вам избежать изменчивости и функциональности прерывания усиления: http://projecteulerfun.blogspot.com/2010/05/problem-7-what-is-10001st-prime-number.html

let problem7a =
    let isPrime n =
        let nsqrt = n |> float |> sqrt |> int
        let rec isPrime i =
            if i > nsqrt then true //break
            elif n % i = 0 then false //break
            //loop while neither of the above two conditions are true
            //pass your state (i+1) to the next call
            else isPrime (i+1) 
        isPrime 2

    let nthPrime n = 
        let rec nthPrime i p count =
            if count = n then p //break
            //loop while above condition not met
            //pass new values in for p and count, emulating state
            elif i |> isPrime then nthPrime (i+2) i (count+1)
            else nthPrime (i+2) p count
        nthPrime 1 1 0

    nthPrime 10001

Теперь конкретно рассмотрим некоторые вопросы, которые у вас возникли в вашем решении.

Вышеприведенная функция nthPrime позволяет вам найти простые числа в произвольной позиции, вот как это будет выглядеть, адаптировано к вашему подходу - найти именно простое число 1001 и использовать имена переменных (решение является хвост-рекурсивным и используйте изменчивые): 

let prime1001 = 
    let rec nthPrime i number accumulator =
        if accumulator = 1001 then number 
        //i is prime, so number becomes i in our next call and accumulator is incremented
        elif i |> isPrime then prime1001 (i+2) i (accumulator+1) 
        //i is not prime, so number and accumulator do not change, just advance i to the next odd
        else prime1001 (i+2) number accumulator
    prime1001 1 1 0

Да, есть лучший способ сделать квадратные корни: напишите свою собственную общую реализацию квадратного корня (ссылка это и эта публикация для реализации G): 

///Finds the square root (integral or floating point) of n
///Does not work with BigRational
let inline sqrt_of (g:G<'a>) n =
    if g.zero = n then g.zero
    else
        let mutable s:'a = (n / g.two) + g.one
        let mutable t:'a = (s + (n / s)) / g.two
        while t < s do
            s <- t
            let step1:'a = n/s
            let step2:'a = s + step1
            t <- step2 / g.two
        s

let inline sqrtG n = sqrt_of (G_of n) n
let sqrtn = sqrt_of gn //this has suffix "n" because sqrt is not strictly integral type
let sqrtL = sqrt_of gL
let sqrtI = sqrt_of gI
let sqrtF = sqrt_of gF
let sqrtM = sqrt_of gM
...