0

Lazy Computation での再帰に問題があります。ニュートン・ラフソン法による平方根の計算が必要です。遅延評価の適用方法がわかりません。これは私のコードです：

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

headandよりも慣用的なパターン マッチングを使用していることに注意してください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

さらに別のアプローチは、 F# PowerPackLazyListから使用することです。コードはこの記事で入手できます。整合性のためにそれを私の答えにコピーします:

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は相対精度ですが、私が見たほとんどの学術書では絶対精度です。2 つの違いはb、ここでは に対して測定されるかどうかです<= eps * abs(b)。FPish のコードは絶対精度epsとして扱われます。
于 2013-04-21T12:10:27.600 に答える