Rfactor這個F＃代碼到尾遞歸

Question

我寫了一些代碼來學習F＃。 這裏有一個例子：

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" 

我很高興，這只是工作！

我完全初學者遞歸

遞歸是一件美妙的事情。我想findPrimes效率不高。

有人幫我重構findPrimes到尾遞歸如果可能？

順便說一句，有沒有更高效的方法來找到第n個素數？

Answer 1

關於你的問題的第一部分，如果你想要寫一個遞歸列表建築功能tail-遞歸地，您應該將中間結果列表作爲函數的一個額外參數傳遞。在你的情況，這將是像

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

遞歸函數AUX收集其結果通稱爲ACC一個額外的參數（如ACC-umulator）。當你達到你的結局條件，只需吐出累計結果。我在另一個函數中包含了尾遞歸輔助函數，所以函數簽名保持不變。

正如您所看到的，對aux的呼叫是n <> 1情況下發生的唯一呼叫，因此也是最後一個呼叫。它現在是尾遞歸的，並將編譯成一個while循環。

我已經定好了你的版本和我的版本，生成了2000個素數。我的版本速度提高了16％，但仍然非常慢。爲了產生素數，我喜歡使用命令式陣列篩。功能不是很好，但非常（非常）快。

Answer 2

爲什麼不乾脆寫：

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 

或篩（非常快）：

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 

Answer 3

另一種方法是使用額外的延續參數使findPrimes尾遞歸。這種技術總是有效的。它會避免堆棧溢出，但可能不會讓你的代碼更快。

此外，我把你的nextPrime函數更接近我使用的風格。

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 

正如其他人所說，有更快的方法來產生素數。

Answer 4

順便說一句，有沒有更有效的方法來找到前n個素數？

我描述了一個快速任意大小的埃拉托色尼的篩在F＃here是累積的成果轉化爲不斷增長的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) 

Answer 5

我知道這是有點晚了，答案是已經接受。但是，我相信一個好的一步一步的指導，可以讓OP或任何其他人對此感興趣。這裏有一些技巧肯定幫了我。因爲，正如其他人所說，我將使用除素數之外的一個橫跨前沿的例子，因爲有更好的方法來產生素數。

考慮一個計數函數的簡單實現，該函數將創建一個從一些n倒數的整數列表。這個版本是不是尾遞歸因此對於長的列表，你會遇到一個堆棧溢出異常：要解決這個問題是使用參數化功能應用延續傳遞風格

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 *) 

方式一：

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 *) 

然後，將此參數化函數重構爲專門的表示形式。請注意，功能countDown'實際上並沒有倒計時。這是在n > 0時繼續建立的方式的神器，然後在n = 0時進行評估。如果你有類似第一個例子的東西，但你不知道如何使它尾部遞歸，我建議你寫第二個，然後嘗試優化它以消除函數參數k。這肯定會提高可讀性。這是第二個例子的優化：

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 []