計算機科学のブログ

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
%