F # lazy recursion

Question

У меня возникли проблемы с рекурсией в Lazy Computations. Мне нужно вычислить квадратный корень методом Ньютона Рафсона. Я не знаю, как применять ленивую оценку. Это мой код:

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