The representation of sequences in terms of lists generalizes naturally to represent sequences whose elements may themselves be sequences. For example, we can regard the object [[1, [2, null]], [3, [4, null]]] constructed by
pair(list(1, 2), list(3, 4));
Another way to think of sequences whose elements are sequences is as
trees. The elements of the sequence are the branches of the
tree, and elements that are themselves sequences are subtrees.
Figure 2.6 shows the structure in
Figure 2.5 viewed as a tree.
Recursion is a natural tool for dealing with tree structures, since we can often reduce operations on trees to operations on their branches, which reduce in turn to operations on the branches of the branches, and so on, until we reach the leaves of the tree. As an example, compare the length function of section 2.2.1 with the count_leaves function, which returns the total number of leaves of a tree:
const x = pair(pair(1, pair(2,null)), pair(3, pair(4,null)));
length(x); // 3
count_leaves(x); // 4
list(x, x); // [[[[1, [2, null]], [3, [4, null]]], // [[[1, [2, null]], [3, [4, null]]], null]]
length(list(x, x)); // 2
count_leaves(list(x, x)); // 8
To implement count_leaves, recall the recursive plan for computing length:
function count_leaves(x) { return is_null(x) ? 0 : ! is_pair(x) ? 1 : count_leaves(head(x)) + count_leaves(tail(x)); }
[1, [3, [[5, [7, null]], [9, null]]]] [[7, null], null] [1, [ [2, [ [3, [ [4, [ [5, [ [6, [7, null ] ], null ] ], null ] ], null ] ], null ] ], null ] ]
head(tail(head(tail(tail(the_first_list)))));
head(head(the_second_list));
head(tail(head(tail(head(tail(head(tail(head( tail(head(tail(the_third_list))))))))))));
const x = list(1, 2, 3); const y = list(4, 5, 6);
append(x, y);
pair(x, y);
list(x, y);
[1, [2, [3, [4, [5, [6, null]]]]]]
[[1, [2, [3, null]]], [4, [5, [6, null]]]]
[[1, [2, [3, null]]], [[4, [5, [6, null]]], null]]
const x = list(list(1, 2), list(3, 4));
x; // [[1, [2, null]], [[3, [4, null]], null]]
reverse(x); // [[3, [4, null]], [[1, [2, null]], null]]
deep_reverse(x); // [[4, [3, null]], [[2, [1, null]], null]]
function deep_reverse(items){ return is_null(items) ? null : is_pair(items) ? append(deep_reverse(tail(items)), pair(deep_reverse(head(items)), null)) : items; }
const x = list(list(1, 2), list(3, 4));
fringe(x); // [1, [2, [3, [4, null]]]]
fringe(list(x, x)); // [1, [2, [3, [4, [1, [2, [3, [4, null]]]]]]]]
function fringe(x) { return is_null(x) ? null : is_pair(x) ? append(fringe(head(x)), fringe(tail(x))) : list(x); }
function make_mobile(left, right) { return list(left, right); }
function make_branch(length, structure) { return list(length, structure); }
function make_mobile(left, right) { return pair(left, right); } function make_branch(length, structure) { return pair(length, structure); }
function left_branch(m) { return head(m); } function right_branch(m) { return head(tail(m)); } function branch_length(b) { return head(b); } function branch_structure(b) { return head(tail(b)); }
function is_weight(x){ return is_number(x); } function total_weight(x) { return is_weight(x) ? x : total_weight(branch_structure( left_branch(x))) + total_weight(branch_structure( right_branch(x))); }
function is_balanced(x) { return is_weight(x) || ( is_balanced(branch_structure( left_branch(x))) && is_balanced(branch_structure( right_branch(x))) && total_weight(branch_structure( left_branch(x))) * branch_length(left_branch(x)) === total_weight(branch_structure( right_branch(x))) * branch_length(right_branch(x)) ); }
function left_branch(m) { return head(m); } function right_branch(m) { return tail(m); } function branch_length(b) { return head(b); } function branch_structure(b) { return tail(b); }
Just as map is a powerful abstraction for dealing with sequences, map together with recursion is a powerful abstraction for dealing with trees. For instance, the scale_tree function, analogous to scale_list of section 2.2.1, takes as arguments a numeric factor and a tree whose leaves are numbers. It returns a tree of the same shape, where each number is multiplied by the factor. The recursive plan for scale_tree is similar to the one for count_leaves:
function scale_tree(tree, factor) { return is_null(tree) ? null : ! is_pair(tree) ? tree * factor : pair(scale_tree(head(tree), factor), scale_tree(tail(tree), factor)); }
Another way to implement scale_tree is to regard the tree as a sequence of sub-trees and use map. We map over the sequence, scaling each sub-tree in turn, and return the list of results. In the base case, where the tree is a leaf, we simply multiply by the factor:
function scale_tree(tree, factor) { return map(sub_tree => is_pair(sub_tree) ? scale_tree(sub_tree, factor) : sub_tree * factor, tree); }
Many tree operations can be implemented by similar combinations of sequence operations and recursion.
square_tree(list(1, list(2, list(3, 4), 5), list(6, 7))); // result: [1, [[4, [[9, [16, null]], // [25, null]]], // [[36, [49, null]], null]]]
function square_tree(tree) { return is_null(tree) ? null : ! is_pair(tree) ? square(tree) : pair(square_tree(head(tree)), square_tree(tail(tree))); }
function square_tree(tree) { return map(sub_tree => ! is_pair(sub_tree) ? square(sub_tree) : square_tree(sub_tree), tree); }
function square_tree(tree) { return tree_map(square, tree); }
function tree_map(f, tree) { return map(sub_tree => is_null(sub_tree) ? null : is_pair(sub_tree) ? tree_map(f, sub_tree) : f(sub_tree), tree); }
[null, [[3, null], [[2, null], [[2, [3, null]], [[1, null], [[2, [3, null]], [[1, [2, null]], [[1, [2, [3, null]]], null]]]]]]]]
function subsets(s) { if (is_null(s)) { return list(null); } else { const rest = subsets(tail(s)); return append(rest, map(??, rest)); } }
function subsets(s) { if (is_null(s)) { return list(null); } else { const rest = subsets(tail(s)); return append(rest, map(x => pair(head(s), x), rest)); } }