計算機科学のブログ

Building Abstractions with Data - Hierarchical Data and the Closure Property - Sequences as Conventional Interfaces - Nested Mappings - flatmap, filter, eight-queens puzzle

Structure and Interpretation of Computer Programs: JavaScript Edition(Harold Abelson(著)、Gerald Jay Sussman(著)、Julie Sussman(著)、The MIT Press)のChapter 2(Building Abstractions with Data)、2.2(Hierarchical Data and the Closure Property)、2.2.3(Sequences as Conventional Interfaces)、Nested Mappings、Exercise 2.42の解答を求めてみる。

コード

function stringfy(x) {
    if (x === undefined) {
        return 'undefined';
    }
    if (is_null(x)) {
        return "null";
    }
    if (is_pair(x)) {
        return "[" + stringfy(head(x)) + ", " + stringfy(tail(x)) + "]";
    }
    return x.toString();
}
function pair(x, y) {
    return [x, y];
}
function head(z) {
    return z[0];
}
function tail(z) {
    return z[1];
}
function is_pair(x) {
    return Array.isArray(x);
}
function is_null(x) {
    return x === null;
}
function list(...args) {
    return args.length === 0 ?
        null :
        pair(args[0], list(...args.slice(1)));
}
function display(x) {
    return console.log(stringfy(x));
}
function length(sequence) {
    return is_null(sequence) ?
        0 :
        1 + length(tail(sequence));
}
function accumulate(op, initial, sequence) {
    return is_null(sequence) ?
        initial :
        op(
            head(sequence),
            accumulate(op, initial, tail(sequence))
        );
}
function map(f, seq) {
    return accumulate((x, y) => pair(f(x), y), null, seq);
}
function filter(pred, seq) {
    if (is_null(seq)) {
        return null;
    }
    const x = head(seq);
    return pred(x) ?
        pair(x, filter(pred, tail(seq))) :
        filter(pred, tail(seq));
}
function append(seq1, seq2) {
    return accumulate(pair, seq2, seq1)
}
function enumerate_interval(low, high) {
    return low > high ?
        null :
        pair(low, enumerate_interval(low + 1, high));
}
function flatmap(f, seq) {
    return accumulate(append, null, map(f, seq));
}
const empty_board = null;
function adjoin_position(row, k, queens) {
    return pair(row, queens);
}
function is_safe(k, positions) {
    function iter(position, rest, n) {
        if (is_null(rest)) {
            return true;
        }
        const i = head(rest);
        return position !== i &&
            position - i != n &&
            i - position != n &&
            iter(position, tail(rest), n + 1);
    }
    return iter(head(positions), tail(positions), 1);
}
function queens(board_size) {
    function queen_cols(k) {
        return k === 0 ?
            list(empty_board) :
            filter(
                positions => is_safe(k, positions),
                flatmap(
                    rest_of_queens => map(
                        new_row =>
                            adjoin_position(
                                new_row,
                                k,
                                rest_of_queens
                            ),
                        enumerate_interval(1, board_size)
                    ),
                    queen_cols(k - 1)
                ),
            );
    }
    return queen_cols(board_size);
}
display(queens(1));
display(queens(2));
display(queens(3));
display(queens(4));
display(queens(8));
display(length(queens(8)));

入出力結果(Terminal, Zsh)

% node answer2.42.js
[[1, null], null]
null
null
[[3, [1, [4, [2, null]]]], [[2, [4, [1, [3, null]]]], null]]
[[4, [2, [7, [3, [6, [8, [5, [1, null]]]]]]]], [[5, [2, [4, [7, [3, [8, [6, [1, null]]]]]]]], [[3, [5, [2, [8, [6, [4, [7, [1, null]]]]]]]], [[3, [6, [4, [2, [8, [5, [7, [1, null]]]]]]]], [[5, [7, [1, [3, [8, [6, [4, [2, null]]]]]]]], [[4, [6, [8, [3, [1, [7, [5, [2, null]]]]]]]], [[3, [6, [8, [1, [4, [7, [5, [2, null]]]]]]]], [[5, [3, [8, [4, [7, [1, [6, [2, null]]]]]]]], [[5, [7, [4, [1, [3, [8, [6, [2, null]]]]]]]], [[4, [1, [5, [8, [6, [3, [7, [2, null]]]]]]]], [[3, [6, [4, [1, [8, [5, [7, [2, null]]]]]]]], [[4, [7, [5, [3, [1, [6, [8, [2, null]]]]]]]], [[6, [4, [2, [8, [5, [7, [1, [3, null]]]]]]]], [[6, [4, [7, [1, [8, [2, [5, [3, null]]]]]]]], [[1, [7, [4, [6, [8, [2, [5, [3, null]]]]]]]], [[6, [8, [2, [4, [1, [7, [5, [3, null]]]]]]]], [[6, [2, [7, [1, [4, [8, [5, [3, null]]]]]]]], [[4, [7, [1, [8, [5, [2, [6, [3, null]]]]]]]], [[5, [8, [4, [1, [7, [2, [6, [3, null]]]]]]]], [[4, [8, [1, [5, [7, [2, [6, [3, null]]]]]]]], [[2, [7, [5, [8, [1, [4, [6, [3, null]]]]]]]], [[1, [7, [5, [8, [2, [4, [6, [3, null]]]]]]]], [[2, [5, [7, [4, [1, [8, [6, [3, null]]]]]]]], [[4, [2, [7, [5, [1, [8, [6, [3, null]]]]]]]], [[5, [7, [1, [4, [2, [8, [6, [3, null]]]]]]]], [[6, [4, [1, [5, [8, [2, [7, [3, null]]]]]]]], [[5, [1, [4, [6, [8, [2, [7, [3, null]]]]]]]], [[5, [2, [6, [1, [7, [4, [8, [3, null]]]]]]]], [[6, [3, [7, [2, [8, [5, [1, [4, null]]]]]]]], [[2, [7, [3, [6, [8, [5, [1, [4, null]]]]]]]], [[7, [3, [1, [6, [8, [5, [2, [4, null]]]]]]]], [[5, [1, [8, [6, [3, [7, [2, [4, null]]]]]]]], [[1, [5, [8, [6, [3, [7, [2, [4, null]]]]]]]], [[3, [6, [8, [1, [5, [7, [2, [4, null]]]]]]]], [[6, [3, [1, [7, [5, [8, [2, [4, null]]]]]]]], [[7, [5, [3, [1, [6, [8, [2, [4, null]]]]]]]], [[7, [3, [8, [2, [5, [1, [6, [4, null]]]]]]]], [[5, [3, [1, [7, [2, [8, [6, [4, null]]]]]]]], [[2, [5, [7, [1, [3, [8, [6, [4, null]]]]]]]], [[3, [6, [2, [5, [8, [1, [7, [4, null]]]]]]]], [[6, [1, [5, [2, [8, [3, [7, [4, null]]]]]]]], [[8, [3, [1, [6, [2, [5, [7, [4, null]]]]]]]], [[2, [8, [6, [1, [3, [5, [7, [4, null]]]]]]]], [[5, [7, [2, [6, [3, [1, [8, [4, null]]]]]]]], [[3, [6, [2, [7, [5, [1, [8, [4, null]]]]]]]], [[6, [2, [7, [1, [3, [5, [8, [4, null]]]]]]]], [[3, [7, [2, [8, [6, [4, [1, [5, null]]]]]]]], [[6, [3, [7, [2, [4, [8, [1, [5, null]]]]]]]], [[4, [2, [7, [3, [6, [8, [1, [5, null]]]]]]]], [[7, [1, [3, [8, [6, [4, [2, [5, null]]]]]]]], [[1, [6, [8, [3, [7, [4, [2, [5, null]]]]]]]], [[3, [8, [4, [7, [1, [6, [2, [5, null]]]]]]]], [[6, [3, [7, [4, [1, [8, [2, [5, null]]]]]]]], [[7, [4, [2, [8, [6, [1, [3, [5, null]]]]]]]], [[4, [6, [8, [2, [7, [1, [3, [5, null]]]]]]]], [[2, [6, [1, [7, [4, [8, [3, [5, null]]]]]]]], [[2, [4, [6, [8, [3, [1, [7, [5, null]]]]]]]], [[3, [6, [8, [2, [4, [1, [7, [5, null]]]]]]]], [[6, [3, [1, [8, [4, [2, [7, [5, null]]]]]]]], [[8, [4, [1, [3, [6, [2, [7, [5, null]]]]]]]], [[4, [8, [1, [3, [6, [2, [7, [5, null]]]]]]]], [[2, [6, [8, [3, [1, [4, [7, [5, null]]]]]]]], [[7, [2, [6, [3, [1, [4, [8, [5, null]]]]]]]], [[3, [6, [2, [7, [1, [4, [8, [5, null]]]]]]]], [[4, [7, [3, [8, [2, [5, [1, [6, null]]]]]]]], [[4, [8, [5, [3, [1, [7, [2, [6, null]]]]]]]], [[3, [5, [8, [4, [1, [7, [2, [6, null]]]]]]]], [[4, [2, [8, [5, [7, [1, [3, [6, null]]]]]]]], [[5, [7, [2, [4, [8, [1, [3, [6, null]]]]]]]], [[7, [4, [2, [5, [8, [1, [3, [6, null]]]]]]]], [[8, [2, [4, [1, [7, [5, [3, [6, null]]]]]]]], [[7, [2, [4, [1, [8, [5, [3, [6, null]]]]]]]], [[5, [1, [8, [4, [2, [7, [3, [6, null]]]]]]]], [[4, [1, [5, [8, [2, [7, [3, [6, null]]]]]]]], [[5, [2, [8, [1, [4, [7, [3, [6, null]]]]]]]], [[3, [7, [2, [8, [5, [1, [4, [6, null]]]]]]]], [[3, [1, [7, [5, [8, [2, [4, [6, null]]]]]]]], [[8, [2, [5, [3, [1, [7, [4, [6, null]]]]]]]], [[3, [5, [2, [8, [1, [7, [4, [6, null]]]]]]]], [[3, [5, [7, [1, [4, [2, [8, [6, null]]]]]]]], [[5, [2, [4, [6, [8, [3, [1, [7, null]]]]]]]], [[6, [3, [5, [8, [1, [4, [2, [7, null]]]]]]]], [[5, [8, [4, [1, [3, [6, [2, [7, null]]]]]]]], [[4, [2, [5, [8, [6, [1, [3, [7, null]]]]]]]], [[4, [6, [1, [5, [2, [8, [3, [7, null]]]]]]]], [[6, [3, [1, [8, [5, [2, [4, [7, null]]]]]]]], [[5, [3, [1, [6, [8, [2, [4, [7, null]]]]]]]], [[4, [2, [8, [6, [1, [3, [5, [7, null]]]]]]]], [[6, [3, [5, [7, [1, [4, [2, [8, null]]]]]]]], [[6, [4, [7, [1, [3, [5, [2, [8, null]]]]]]]], [[4, [7, [5, [2, [6, [1, [3, [8, null]]]]]]]], [[5, [7, [2, [6, [3, [1, [4, [8, null]]]]]]]], null]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
92
%