How to refactor F# code to not use a mutable accumulator?

Question

The following F# code gives the correct answer to Project Euler problem #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. I'd like to avoid the mutable values accumulator and number. I'd also like to refactor the while loop into a tail recursive function. Any tips?
2. Any ideas on how to remove the (number - 1) kludge which displays the result?
3. Any general comments about this code or suggestions on how to improve it?

Answer 1

You can refer my F# for Project Euler Wiki:

I got this first 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
                           // ~~ 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

In this version, although looks nicer, but I still does not early break the loop when the number is not a prime. In Seq module, exist and forall methods support early stop:

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)

Notice in this version of isPrime, the function is finally mathematically correct by checking numbers below 2.

Or you can use a tail recursive function to do the while loop:

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

A more functional version of problem7 is to use Seq.unfold to generate an infinite prime sequence and take nth element of this sequence:

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

Answer 2

Here's my solution, which uses a tail-recursive loop pattern which always allows you to avoid mutables and gain break functionality: 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

Now, to specifically address some of the questions you had in your solution.

The above nthPrime function allows you to find primes at an arbitrary position, this is how it would look adapted to your approach of finding specifically the 1001 prime, and using your variable names (the solution is tail-recursive and doesn't use mutables):

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

Yes, there is a better way to do square roots: write your own generic square root implementation (reference this and this post for G implementation):

///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

Answer 3

Loops are nice, but its more idiomatic to abstract away loops as much as possible.

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

Sequences are your friend :)