Exercise1-45 <---
Exercise 1.46
Several of the numerical methods described in this chapter are instances of an extremely general computational strategy known as iterative improvement. Iterative improvement says that, to compute something, we start with an initial guess for the answer, test if the guess is good enough, and otherwise improve the guess and continue the process using the improved guess as the new guess. Write a procedure iterative-improve that takes two procedures as arguments: a method for telling whether a guess is good enough and a method for improving a guess. iterative-improve should return as its value a procedure that takes a guess as argument and keeps improving the guess until it is good enough. Rewrite the sqrt procedure of section 1.1.7 and the fixed-point procedure of section 1.3.3 in terms of iterative-improve.
Ru: Русский текст упражнения
Scheme solution:
(define (iterative-improve good-enough? improve-guess)
(lambda (guess)
(define (iter guess)
(let ((next (improve-guess guess)))
(if (good-enough? guess next)
next
(iter next))))
(iter guess)))
(define (sqrt x)
((iterative-improve (lambda (g n)
(< (abs (- (* n n) x)) 0.0001))
(lambda (g)
(/ (+ g (/ x g)) 2)))
1.0))
(define (fixed-point f first-guess)
((iterative-improve (lambda (g n)
(< (abs (- g n)) 0.00001))
f)
first-guess))
Haskell solution:
iterative_improve good_enough improve_guess guess = iter guess
where iter guess | good_enough guess next = next
| otherwise = iter next
where next = improve_guess guess
sqrt x = iterative_improve (\g n -> abs (n*n - x) < 0.0001)
(\g -> (g + x/g) / 2)
1
fixed_point f first_guess =
iterative_improve (\g n -> abs (g-n) < 0.00001)
f
first_guess
OCaml solution:
let iterative_improve good_enough improve_guess guess =
let rec iter guess =
let next = improve_guess guess in
if good_enough guess next then
next
else
iter next
in
iter guess
let sqrt x =
iterative_improve (fun g n -> abs_float (n *. n -. x) < 0.0001)
(fun g -> (g +. x /. g) /. 2.)
1.
let fixed_point f first_guess =
iterative_improve (fun g n -> abs_float (g -. n) < 0.00001)
f
first_guess
Standard ML solution:
fun iterative_improve (good_enough, improve_guess, guess) = let
fun iter guess = let
val next = improve_guess guess
in
if good_enough (guess, next) then
next
else
iter next
end
in
iter guess
end
fun sqrt x =
iterative_improve (fn (g, n) => abs (n*n - x) < 0.0001,
fn g => (g + x/g) / 2.0,
1.0)
fun fixed_point (f, first_guess) =
iterative_improve (fn (g, n) => abs (g - n) < 0.00001,
f,
first_guess)
Other solutions goes here (use "#!code haskell", "#!code ocaml", etc. for syntax highlighting)
Exercise1-45 <---