0

我在惰性计算中的递归有一些问题。我需要通过 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;

当然，堆栈溢出异常。

4

2 回答 2

3

您正在使用具有热切评估的 F# 列表。在您的示例中，您需要延迟评估和分解列表，因此F# PowerPack 的 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请注意，我使用了比and更惯用的模式匹配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
于 2013-04-21T12:12:24.510 回答
2

如果您需要惰性计算，那么您必须使用适当的工具。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

另一种方法是使用LazyListF # PowerPack。该代码可在本文中找到。为了完整性，将其复制到我的答案中：

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绝对准确度。
于 2013-04-21T12:10:27.600 回答