Exercise1-30 <---> Exercise1-32
Exercise 1.31
a. The sum procedure is only the simplest of a vast number of similar abstractions that can be captured as higher-order procedures. Write an analogous procedure called product that returns the product of the values of a function at points over a given range. Show how to define factorial in terms of product. Also use product to compute approximations to 
using the formula:
b. If your product procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.
Ru: а. Процедура sum - всего лишь простейшая из обширного множества подобных абстракций, которые можно выразить через процедуры высших порядков. Напишите аналогичную процедуру под названием product, которая вычисляет произведение значений функции в точках на указанном интервале. Покажите, как с помощью этой процедуры определить factorial. Кроме того, при помощи product вычислите приближенное значение по формуле
b. Если Ваша процедура product порождает рекурсивный процесс, перепишите её так, чтобы она порождала итеративный. Если она порождает итеративный процесс, перепишите её так, чтобы она порождала рекурсивный.
Scheme solution:
;; 'a' section
(define (product-rec term a next b) ;; recursive process
(if (> a b)
1
(* (term a) (product-rec term (next a) next b))))
(define (id x) x)
(define (factorial n)
(product-rec id 1 inc n))
(define (pi-product n)
(define (pi-term k)
(/ (* (- k 1) (+ k 1))
(* k k)))
(define (inc2 k) (+ k 2))
(* 4.0
(product-rec pi-term 3 inc2 n)))
;; 'b' section
(define (product-iter term a next b) ;; iterative process
(define (iter a result)
(if (> a b)
result
(iter
(next a)
(* result (term a)))))
(iter a 1))
Haskell solution:
(Standard Prelude function product products all elements in list.)
a section:
product'rec [] = 1
product'rec (x:xs) = x * product'rec xs
factorial n = product'rec [1..n]
calc'pi n = 4 * (product'rec $ take n $ map (\(x,y) -> x/y) xys)
where
xys = concat[[(k-1, k), (k+1, k)] | k <- [3, 5..]]
b section:
product'iter xs = product' xs 1
where
product' [] v = v
product' (x:xs) v = product' xs $! (x*v)
Oberon/Component Pascal solution:
a section:
PROCEDURE ProductRec (term : PROCEDURE (X : REAL) : REAL;
next : PROCEDURE (X : REAL) : REAL;
a, b : REAL) : REAL;
VAR c : REAL;
BEGIN
IF a > b THEN
c := 1
ELSE
c := term (a) * ProductRec (term, next, next(a), b)
END;
RETURN c
END ProductRec;
PROCEDURE Id (x : REAL) : REAL;
BEGIN
RETURN x
END Id;
PROCEDURE Inc (x : REAL) : REAL;
BEGIN
RETURN x + 1
END Inc;
PROCEDURE Factorial (n : REAL) : REAL;
BEGIN
RETURN ProductRec (Id, Inc, 1, n)
END Factorial;
PROCEDURE PiTerm (k : REAL) : REAL;
BEGIN
RETURN ((k-1)/k) * ((k+1)/k)
END PiTerm;
PROCEDURE Inc2 (x : REAL) : REAL;
BEGIN
RETURN x + 2
END Inc2;
PROCEDURE PiCalc (n : REAL) : REAL;
BEGIN
RETURN 4 * ProductRec (PiTerm, Inc2, 3, n)
END PiCalc;
b section:
PROCEDURE ProductIter (term : PROCEDURE (X : REAL) : REAL;
next : PROCEDURE (X : REAL) : REAL;
a, b : REAL) : REAL;
VAR next_a, c : REAL;
BEGIN
next_a := a; c := 1;
WHILE next_a <= b DO
c := c * term (next_a);
next_a := next (next_a)
END;
RETURN c
END ProductIter;
Exercise1-30 <---> Exercise1-32
Comments
| I like the idea of the pi-term function to produce a cleaner solution, but I think it might also create some problems. For example, although the pi-product procedure for Scheme would calculate approximations for pi, it seems like a possible problem that the n value doesn't correspond in a straight-forward way with the precision of the approximation that the procedure is going to return. For example, n = 1 gives you an approximation of 0, rather than 8/3, and all even values of n are going to create nonsense. Any thoughts on how to keep the neatness of the pi-term function while allowing the n value to correspond directly to the number of factors in the numerator of the approximation? | ||||
| Posted by c-76-126-141-160 at 2008-07-08 20:26:29 X | ||||