Wie refactor man F#-Code, um keinen veränderbaren Akkumulator zu verwenden?

Question

Der folgende F#-Code liefert die richtige Antwort auf Project Euler Problem #7:

let isPrime num =
    let upperDivisor = int32(sqrt(float num))   // Gibt es einen besseren Weg?
    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   // Möchte vermeiden, veränderbare Werte zu verwenden.
let mutable number = 2        // ""

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

printfn "Die 10001. Primzahl ist %i." (number - 1)  // Fühlt sich holprig an.
printfn ""
printfn "Drücken Sie eine beliebige Taste, um fortzufahren."
System.Console.ReadKey() |> ignore

1. Ich möchte die Verwendung der mutable-Werte accumulator und number vermeiden. Außerdem möchte ich die while-Schleife in eine endrekursive Funktion umgestalten. Irgendwelche Tipps?
2. Habt ihr Ideen, wie man das Kludern mit (number - 1) entfernen könnte, um das Ergebnis anzuzeigen?
3. Irgendwelche allgemeinen Anmerkungen zu diesem Code oder Vorschläge zur Verbesserung?

Answer 1

Schleifen sind schön, aber es ist idiomatischer, Schleifen so weit wie möglich abstrahiert zu halten.

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 "Die 10001. Primzahl ist %i." (nthPrime 10001)
printfn ""
printfn "Drücke eine beliebige Taste, um fortzufahren."
System.Console.ReadKey() |> ignore

Sequenzen sind dein Freund :)

Answer 2

Sie können in meinem F# für das Projekt Euler Wiki nachschlagen:

Ich habe diese erste Version:

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
                           // ~~ Ich möchte hier abbrechen!
        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

In dieser Version sieht es zwar besser aus, aber ich breche den Loop immer noch nicht frühzeitig ab, wenn die Zahl keine Primzahl ist. In Seq-Modulen existieren und unterstützen die Methoden exist und forall ein vorzeitiges Stoppen:

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
        // oder äquivalent:
        // {2..m} |> Seq.forall (fun i->n%i<>0)

Beachten Sie in dieser Version von isPrime, dass die Funktion endlich mathematisch korrekt ist, indem sie Zahlen unter 2 überprüft.

Oder Sie können eine endrekursive Funktion verwenden, um die while-Schleife auszuführen:

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

Eine funktionalere Version von problem7 besteht darin, Seq.unfold zu verwenden, um eine unendliche Primzahlsequenz zu generieren und das n-te Element dieser Sequenz zu nehmen:

let problem7b =
    let primes =
        2 |> Seq.unfold (fun p ->
            let next = nextPrime (p+1) in
            Some( p, next ) )
    Seq.nth 10000 primes

Answer 3

Hier ist meine Lösung, die ein tail-rekursives Schleifenmuster verwendet, das es immer ermöglicht, mutable Variablen zu vermeiden und eine Break-Funktionalität zu erlangen: 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

Um nun einige der Fragen in Ihrer Lösung speziell zu beantworten.

Die obige nthPrime Funktion ermöglicht es Ihnen, Primzahlen an einer beliebigen Position zu finden. So würde sie aussehen, angepasst an Ihren Ansatz, speziell die 1001. Primzahl zu finden und unter Verwendung Ihrer Variablennamen (die Lösung ist tail-rekursiv und verwendet keine mutablen Variablen):

let prime1001 = 
    let rec nthPrime i number accumulator =
        if accumulator = 1001 then number 
        //i ist eine Primzahl, daher wird number in unserem nächsten Aufruf zu i und accumulator wird erhöht
        elif i |> isPrime then prime1001 (i+2) i (accumulator+1) 
        //i ist keine Primzahl, also ändern sich number und accumulator nicht, nur i wird auf die nächste ungerade Zahl fortgeschrieben
        else prime1001 (i+2) number accumulator
    prime1001 1 1 0

Ja, es gibt einen besseren Weg, um Quadratwurzeln zu berechnen: Schreiben Sie Ihre eigene generische Quadratwurzelimplementierung (siehe diesen und diesen Beitrag für die G-Implementierung):

///Ermittelt die Quadratwurzel (ganzzahlig oder Gleitkommazahl) von n
///Funktioniert nicht mit 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 //dies hat das Suffix "n", da sqrt nicht strikt ganzzahligen Typ hat
let sqrtL = sqrt_of gL
let sqrtI = sqrt_of gI
let sqrtF = sqrt_of gF
let sqrtM = sqrt_of gM