Solution to Exercise 3.17

[clean99]

function count_pairs(x) {
    let counted_pairs = null;
    function is_counted_pair(counted_pairs, x) {
        return is_null(counted_pairs)
               ? false
               : head(counted_pairs) === x
               ? true
               : is_counted_pair(tail(counted_pairs), x);
    }
    
    function count(x) {
        if(! is_pair(x) || is_counted_pair(counted_pairs, x)) {
            return 0;
        } else {
            counted_pairs = pair(x, counted_pairs);
            return count(head(x)) +
                   count(tail(x)) +
                   1;
        }
    }
    
    return count(x);
}

[asukaminato0721]

my version:

for test, leak the abstraction

const three_list = ["a", ["b", ["c", undefined]]];

const make_cycle = (x) => {
    x[x.length - 1] = x;
    return x;
};

const one = ["a", "b"];
const three = [one, one];
const four = [three, "c"];
const seven = [three, three];

const memq = (x, y) => {
    if (y === undefined) {
        return false;
    }
    if (x === y[0]) {
        return y;
    }
    return memq(x, y[1]);
}
function fixed_count_pairs(x) {
    let visited = undefined;
    function dfs(x) {
        if (Array.isArray(x) && !memq(x, visited)) {
            visited = [x, visited];
            return dfs(x[0]) + dfs(x[1]) + 1;
        }
        return 0;
    }
    return dfs(x);
}
console.log(
    fixed_count_pairs(three_list),
    fixed_count_pairs(one),
    fixed_count_pairs(three),
    fixed_count_pairs(seven), // since [three, three] is the same.
    fixed_count_pairs(make_cycle(three)));

const memq = (x, y) => {
    if (is_null(y)) {
        return false;
    }
    if (x === head(y)) {
        return true;
    }
    return memq(x, tail(y));
}
function fixed_count_pairs(x) {
    let visited = undefined;
    function dfs(x) {
        if (is_pair(x) && !memq(x, visited)) {
            visited = pair(x, visited);
            return dfs(head(x)) + dfs(tail(x)) + 1;
        }
        return 0;
    }
    return dfs(x);
}