F＃懶惰遞歸

Question

我在Lazy Computations中有一些遞歸問題。我需要用Newton Raphson方法計算平方根。我不知道如何應用懶惰的評估。這是我的代碼：

let next x z = ((x + z/x)/2.); 
let rec iterate f x = 
    List.Cons(x, (iterate f (f x))); 

let rec within eps list = 
    let a = float (List.head list); 
    let b = float (List.head (List.tail list)); 
    let rest = (List.tail (List.tail (list))); 
    if (abs(a - b) <= eps * abs(b)) 
     then b 
     else within eps (List.tail (list)); 
let lazySqrt a0 eps z = 
    within eps (iterate (next z) a0); 

let result2 = lazySqrt 10. Eps fvalue; 
printfn "lazy approach"; 
printfn "result: %f" result2; 

當然，堆棧溢出異常。

Answer 1

如果您需要懶惰計算，那麼你必須使用適當的工具。 List是不懶惰，它被計算爲終點。你的iterate函數永遠不會結束，所以整個代碼堆棧在這個函數中溢出。

您可以在這裏使用Seq。
注意：Seq.skip幾乎不可避免地會導致您的複雜性O（N^2）。

let next N x = ((x + N/x)/2.); 
let rec iterate f x = seq { 
    yield x 
    yield! iterate f (f x) 
} 

let rec within eps list = 
    let a = Seq.head list 
    let b = list |> Seq.skip 1 |> Seq.head 
    if (abs(a - b) <= eps * abs(b)) 
     then b 
     else list |> Seq.skip 1 |> within eps 
let lazySqrt a0 eps z = 
    within eps (iterate (next z) a0); 

let result2 = lazySqrt 10. 0.0001 42.; 
printfn "lazy approach"; 
printfn "result: %f" result2; 
// 6.4807406986501 

---

另一種方法是使用LazyList從F# PowerPack。該代碼可在this article獲得。它複製到我的回答對誠信的緣故：

open Microsoft.FSharp.Collections.LazyList 

let next N (x:float) = (x + N/x)/2.0 

let rec repeat f a = 
    LazyList.consDelayed a (fun() -> repeat f (f a)) 

let rec within (eps : float) = function 
    | LazyList.Cons(a, LazyList.Cons(b, rest)) when (abs (a - b)) <= eps -> b 
    | x -> within eps (LazyList.tail x) 

let newton_square a0 eps N = within eps (repeat (next N) a0) 

printfn "%A" (newton_square 16.0 0.001 16.0) 

些小的便籤：

• 你next功能是錯誤的;
• eps的含義是相對準確性雖然在大多數學術書籍中我看過絕對精度。兩者之間的區別在於它是否根據b進行測量，這裏是：<= eps * abs(b)。來自FPish的代碼將eps視爲絕對精度。

Answer 2

您正在使用急於評估的F＃列表。在你的榜樣，你需要懶惰的評價和分解列表，所以F# PowerPack's LazyList是適合使用：

let next z x = (x + z/x)/2. 

let rec iterate f x = 
    LazyList.consDelayed x (fun() -> iterate f (f x)) 

let rec within eps list = 
    match list with 
    | LazyList.Cons(a, LazyList.Cons(b, rest)) when abs(a - b) <= eps * abs(b) -> b 
    | LazyList.Cons(a, res) -> within eps res 
    | LazyList.Nil -> failwith "Unexpected pattern" 

let lazySqrt a0 eps z = 
    within eps (iterate (next z) a0) 

let result2 = lazySqrt 10. Eps fvalue 
printfn "lazy approach" 
printfn "result: %f" result2 

請注意，我用的模式匹配比head和tail更地道。

如果你不介意稍微不同的方法，Seq.unfold自然在這裏：

let next z x = (x + z/x)/2. 

let lazySqrt a0 eps z = 
    a0 
    |> Seq.unfold (fun a -> 
      let b = next z a 
      if abs(a - b) <= eps * abs(b) then None else Some(a, b)) 
    |> Seq.fold (fun _ x -> x) a0