Rfactor this F# code to tail recursion

I write 开发者_Go百科some code to learning F#. Here is a example:

let nextPrime list=
    let rec loop n=
        match n with
        | _ when (list |> List.filter (fun x -> x <= ( n |> double |> sqrt |> int)) |> List.forall (fun x -> n % x <> 0)) -> n
        | _ -> loop (n+1)
    loop (List.max list + 1)

let rec findPrimes num=
    match num with
    | 1 -> [2]
    | n -> 
        let temp = findPrimes <| n-1
        (nextPrime temp ) :: temp

//find 10 primes
findPrimes 10 |> printfn "%A"

I'm very happy that it just works!

I'm totally beginner to recursion

Recursion is a wonderful thing.

I think findPrimes is not efficient.

Someone help me to refactor findPrimes to tail recursion if possible?

BTW, is there some more efficient way to find first n primes?

---

Regarding the first part of your question, if you want to write a recursive list building function tail-recursively you should pass the list of intermediate results as an extra parameter to the function. In your case this would be something like

let findPrimesTailRecursive num =
    let rec aux acc num = 
        match num with
        | 1 -> acc
        | n -> aux ((nextPrime acc)::acc) (n-1)
    aux [2] num

The recursive function aux gathers its results in an extra parameter conveniently called acc (as in acc-umulator). When you reach your ending condition, just spit out the accumulated result. I've wrapped the tail-recursive helper function in another function, so the function signature remains the same.

As you can see, the call to aux is the only, and therefore last, call to happen in the n <> 1 case. It's now tail-recursive and will compile into a while loop.

I've timed your version and mine, generating 2000 primes. My version is 16% faster, but still rather slow. For generating primes, I like to use an imperative array sieve. Not very functional, but very (very) fast.

---

An alternative is to use an extra continuation argument to make findPrimes tail recursive. This technique always works. It will avoid stack overflows, but probably won't make your code faster.

Also, I put your nextPrime function a little closer to the style I'd use.

let nextPrime list=
    let rec loop n = if list |> List.filter (fun x -> x*x <= n) 
                             |> List.forall (fun x -> n % x <> 0) 
                     then n
                     else loop (n+1)
    loop (1 + List.head list)

let rec findPrimesC num cont =
        match num with
        | 1 -> cont [2]
        | n -> findPrimesC (n-1) (fun temp -> nextPrime temp :: temp |> cont)

let findPrimes num = findPrimesC num (fun res -> res)        
findPrimes 10

As others have said, there's faster ways to generate primes.

---

Why not simply write:

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

let findPrimes n = 
    {2..n} |> Seq.filter isPrime |> Seq.toList

or sieve (very fast):

let generatePrimes max=
    let p = Array.create (max+1) true
    let rec filter i step = 
        if i <= max then 
            p.[i] <- false
            filter (i+step) step
    {2..int (sqrt (float max))} |> Seq.iter (fun i->filter (i+i) i) 
    {2..max} |> Seq.filter (fun i->p.[i]) |> Seq.toArray

---

BTW, is there some more efficient way to find first n primes?

I described a fast arbitrary-size Sieve of Eratosthenes in F# here that accumulated its results into an ever-growing ResizeArray:

> let primes =
    let a = ResizeArray[2]
    let grow() =
      let p0 = a.[a.Count-1]+1
      let b = Array.create p0 true
      for di in a do
        let rec loop i =
          if i<b.Length then
            b.[i] <- false
            loop(i+di)
        let i0 = p0/di*di
        loop(if i0<p0 then i0+di-p0 else i0-p0)
      for i=0 to b.Length-1 do
        if b.[i] then a.Add(p0+i)
    fun n ->
      while n >= a.Count do
        grow()
      a.[n];;
val primes : (int -> int)

---

I know that this is a bit late, and an answer was already accepted. However, I believe that a good step by step guide to making something tail recursive may be of interest to the OP or anyone else for that matter. Here are some tips that have certainly helped me out. I'm going to use a strait-forward example other than prime generation because, as others have stated, there are better ways to generate primes.

Consider a naive implementation of a count function that will create a list of integers counting down from some n. This version is not tail recursive so for long lists you will encounter a stack overflow exception:

let rec countDown = function
  | 0 -> []
  | n -> n :: countDown (n - 1)
(*         ^
           |... the cons operator is in the tail position
                as such it is evaluated last.  this drags
                stack frames through subsequent recursive
                calls *)

One way to fix this is to apply continuation passing style with a parameterized function:

let countDown' n =
  let rec countDown n k =
    match n with
    | 0 -> k [] (*            v--- this is continuation passing style *)
    | n -> countDown (n - 1) (fun ns -> n :: k ns)
(*          ^
            |... the recursive call is now in tail position *)
  countDown n (fun ns -> ns) 
(*              ^
                |... and we initialize k with the identity function *)

Then, refactor this parameterized function into a specialized representation. Notice that the function countDown' is not actually counting down. This is an artifact of the way the continuation is built up when n > 0 and then evaluated when n = 0. If you have something like the first example and you can't figure out how to make it tail recursive, what I'm suggesting is that you write the second one and then try to optimize it to eliminate the function parameter k. That will certainly improve the readability. This is an optimization of the second example:

let countDown'' n =
  let rec countDown n ns =
    match n with
    | 0 -> List.rev ns  (* reverse so we are actually counting down again *)
    | n -> countDown (n - 1) (n :: ns)
  countDown n []