Exercise1-31 <---> Exercise1-33
Exercise 1.32
a. Show that sum and product (exercise 1.31) are both special cases of a still more general notion called accumulate that combines a collection of terms, using some general accumulation function:
(accumulate combiner null-value term a next b)
Accumulate takes as arguments the same term and range specifications as sum and product, together with a combiner procedure (of two arguments) that specifies how the current term is to be combined with the accumulation of the preceding terms and a null-value that specifies what base value to use when the terms run out. Write accumulate and show how sum and product can both be defined as simple calls to accumulate.
b. If your accumulate 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 (упражнение 1.31) являются частными случаями еще более общего понятия, называемого накопление (accumulation), которое комбинирует множество термов с помощью некоторой общей функции накопления
(accumulate combiner null-value term a next b)
accumulate принимает в качестве аргументов те же описания термов и диапазона, что и sum с product, а еще процедуру combiner (двух аргументов), которая указывает, как нужно присоединить текущий терм к результату накопления предыдущих, и null-value, базовое значение, которое нужно использовать, когда термы закончатся. Напишите accumulate и покажите, как и sum, и product можно определить в виде простых вызовов accumulate.
б. Если Ваша процедура accumulate порождает рекурсивный процесс, перепишите ее так, чтобы она порождала итеративный. Если она порождает итеративный процесс, перепишите ее так, чтобы она порождала рекурсивный.
Scheme solution:
(define (accumulate-rec combiner null-value term a next b)
(if (> a b)
null-value
(combiner (term a)
(accumulate-rec combiner null-value term (next a) next b))))
(define (sum-acc term a next b)
(accumulate-rec + 0 term a next b))
(define (product-acc term a next b)
(accumulate-rec * 1 term a next b))
(define (accumulate-iter combiner null-value term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a)
(combiner result (term a)))))
(iter a null-value))
Haskell solution:
accumulate'rec combiner null'value term a next b
| a > b = null'value
| otherwise = combiner (term a)
(accumulate'rec combiner null'value term (next a) next b)
sum'acc term a next b = accumulate'rec (+) 0 term a next b
product'acc term a next b = accumulate'rec (*) 1 term a next b
-- Variants:
-- sum'acc = accumulate'rec (+) 0
-- product'acc = accumulate'rec (*) 1
accumulate'iter combiner null'value term a next b = iter a null'value
where
iter a result | a > b = result
| otherwise = iter (next a) (combiner result (term a))
Прим. Эти решения не являются идиоматичными для Хаскелла, в котором подобные процессы принято выражать в виде обработки списков чисел. Например, суммирование результатов обработки чисел от a до b функцией term в Хаскелле следовало бы выполнить так: сначала создаём список значений от a до b с шагом, задаваемым функцией next, затем обработаем его функцией term и полученный список просуммируем поэлементно
acc'list combiner null'value [] = null'value
acc'list combiner null'value (x:xs) = combiner x (acc'list combiner null'value xs)
sum'acc term a next b = acc'list (+) 0 (map term [a, (next a)..b])
product'acc term a next b = acc'list (*) 1 (map term [a, (next a)..b])
В Хаскелле имеются стандартные функции обработки списка с накоплением результата - foldr (свёртка списка справа налево), foldl (свёртка списка слева направо), а также некоторые другие... Суммирование и перемножение списков с использованием, например, функции foldr, выглядит так:
sum xs = foldr (+) 0 xs
product xs = foldr (*) 1 xs
OCaml solution:
let rec accumulate_rec combiner null_value term a next b =
if a > b then
null_value
else
combiner (term a)
(accumulate_rec combiner null_value term (next a) next b)
let sum_int_acc term a next b = accumulate_rec (+) 0 term a next b
let product_int_acc term a next b = accumulate_rec ( * ) 1 term a next b
let accumulate_iter combiner null_value term a next b =
let rec iter a result =
if a > b then
result
else
iter (next a) (combiner result (term a))
in
iter a null_value
В Хаскелле имеются стандартные функции обработки списка с накоплением результата - List.fold_right (свёртка списка справа налево), List.fold_left (свёртка списка слева направо), а также некоторые другие... Суммирование и перемножение списков с использованием, например, функции List.fold_right, выглядит так:
let sum_int xs = List.fold_right (+) xs 0
let product_int xs = List.fold_right ( * ) xs 1
Standard ML solution:
fun accumulate_rec (combiner, null_value, term, a, next, b) =
if a > b then
null_value
else
combiner (term a,
accumulate_rec (combiner, null_value, term, next a, next, b))
fun sum_int_acc (term, a, next, b) = accumulate_rec (op +, 0, term, a, next, b)
fun product_int_acc (term, a, next, b) = accumulate_rec (op *, 1, term, a, next, b)
fun accumulate_iter (combiner, null_value, term, a, next, b) = let
fun iter (a, result) =
if a > b then
result
else
iter (next a, combiner (result, term a))
in
iter (a, null_value)
end
В Хаскелле имеются стандартные функции обработки списка с накоплением результата - foldr (свёртка списка справа налево), foldl (свёртка списка слева направо), а также некоторые другие... Суммирование и перемножение списков с использованием, например, функции foldr, выглядит так:
fun sum_int xs = foldr op + 0 xs
fun product_int xs = foldr op * 1 xs
Oberon/Component Pascal solution:
PROCEDURE AccumulateRec (combiner : PROCEDURE (x, y : REAL) : REAL;
nullValue : REAL;
term : PROCEDURE (x : REAL) : REAL;
a : REAL;
next : PROCEDURE (x : REAL) : REAL;
b : REAL) : REAL;
VAR c : REAL;
BEGIN
IF a > b THEN
c := nullValue
ELSE
c := combiner (term (a),
AccumulateRec (combiner, nullValue, term, next(a), next, b))
END;
RETURN c
END AccumulateRec;
PROCEDURE Add (x, y : REAL) : REAL;
BEGIN
RETURN x + y
END Add;
PROCEDURE Mul (x, y : REAL) : REAL;
BEGIN
RETURN x * y
END Mul;
PROCEDURE SumAcc (term : PROCEDURE (x : REAL) : REAL;
a : REAL;
next : PROCEDURE (x : REAL) : REAL;
b : REAL) : REAL;
BEGIN
RETURN AccumulateRec (Add, 0, term, a, next, b)
END SumAcc;
PROCEDURE ProductAcc (term : PROCEDURE (x : REAL) : REAL;
a : REAL;
next : PROCEDURE (x : REAL) : REAL;
b : REAL) : REAL;
BEGIN
RETURN AccumulateRec (Mul, 1, term, a, next, b)
END ProductAcc;
PROCEDURE AccumulateIter (combiner : PROCEDURE (x, y : REAL) : REAL;
nullValue : REAL;
term : PROCEDURE (x : REAL) : REAL;
a : REAL;
next : PROCEDURE (x : REAL) : REAL;
b : REAL) : REAL;
VAR next_a, c : REAL;
BEGIN
next_a := a; c := nullValue;
WHILE next_a <= b DO
c := combiner (c, term (next_a));
next_a := next (next_a)
END;
RETURN c
END AccumulateIter;
Exercise1-31 <---> Exercise1-33