計算機科学のブログ

function stringfy(x) {
    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 list(...args) {
    return args.length === 0 ?
        null :
        pair(args[0], list(...args.slice(1)));
}
function length(x) {
    function iter(x, n) {
        return is_null(x) ?
            n :
            iter(tail(x), n + 1);
    }
    return iter(x, 0);
}
function display(x) {
    return console.log(stringfy(x));
}
function is_null(x) {
    return x === null;
}
function count_leaves(x) {
    return is_null(x) ?
        0 :
        is_pair(x) ?
            count_leaves(head(x)) + count_leaves(tail(x)) :
            1;
}
const x = pair(list(1, 2), list(3, 4));
display(x);
display(length(x));
display(count_leaves(x));

const y = list(1, list(2, list(3, 4)));

display(y);
// length 2
display(length(y));
// leaves 4
display(count_leaves(y));

function print_tree(x) {
    const prefix = "  ";
    function iter(y, indent) {
        if (is_null(y)) {
            return;
        }
        if (is_pair(y)) {
            iter(head(y), indent + 1);
            return iter(tail(y), indent + 1);
        }
        return display(prefix.repeat(indent) + stringfy(y));
    }
    return iter(x, 0);
}
display("");
print_tree(x);
display("");
print_tree(y);

% node answer2.24.js
[[1, [2, null]], [3, [4, null]]]
3
4
[1, [[2, [[3, [4, null]], null]], null]]
2
4

    1
      2
    3
      4

  1
      2
          3
            4
%