Building Abstractions with Functions - Formulating Abstractions with Higher-Order Functions - Functions as Arguments - accumlate function, filtering, gcd
Structure and Interpretation of Computer Programs: JavaScript Edition(Harold Abelson(著)、Gerald Jay Sussman(著)、Julie Sussman(著)、The MIT Press)のChapter 1(Building Abstractions with Functions)、1.3(Formulating Abstractions with Higher-Order Functions)、1.3.1(Functions as Arguments)、Exercise 1.33の解答を求めてみる。
コード
function filtered_accumulate(filter, combiner, null_value, term, a, next, b) {
function iter(n, result) {
return n > b ?
result :
filter(n) ?
iter(next(n), combiner(result, term(n))) :
iter(next(n), result);
}
return iter(a, null_value);
}
console.log('a');
function is_even(n) {
return n % 2 === 0;
}
function math_floor(x) {
return Math.floor(x);
}
function math_random() {
return Math.random();
}
function expmod(base, exp, m) {
function nontrivial_square_root_signal(n) {
let r = square(n) % m;
return n !== 1 && n !== m - 1 && r === 1 ?
0 :
r;
}
return exp === 0 ?
1 :
is_even(exp) ?
nontrivial_square_root_signal(expmod(base, exp / 2, m)) :
(base * expmod(base, exp - 1, m)) % m;
}
function miller_rabin_test(n) {
function try_it(a) {
return expmod(a, n, n) === a;
}
return try_it(1 + math_floor(math_random() * (n - 1)));
}
function fast_is_prime(n, times) {
return times === 0 ?
true :
miller_rabin_test(n) ?
fast_is_prime(n, times - 1) :
false;
}
function is_prime(n) {
return fast_is_prime(n, 10);
}
function add(x, y) {
return x + y;
}
function inc(x) {
return x + 1;
}
function square(x) {
return x * x;
}
function sum_of_squares_primes(a, b) {
return filtered_accumulate(is_prime, add, 0, square, a, inc, b);
}
console.log(sum_of_squares_primes(2, 10));
console.log(sum_of_squares_primes(2, 12));
console.log('b.');
function gcd(a, b) {
let r = a % b;
return r === 0 ?
b :
gcd(b, r);
}
function mul(x, y) {
return x * y;
}
function identity(x) {
return x;
}
function product_postive_less_n_prime_n(n) {
function filter(i) {
return gcd(i, n) === 1;
}
return filtered_accumulate(filter, mul, 1, identity, 1, inc, n);
}
console.log(product_postive_less_n_prime_n(10));
console.log(product_postive_less_n_prime_n(15));
console.log(product_postive_less_n_prime_n(20));
入出力結果(Terminal, Zsh)
% node answer1.33.js
a
87
208
b.
189
896896
8729721
%