2.2.2 Hierarchical Structures - SICP Comparison Edition

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));

as a list of three items, the first of which is itself a list, [1, [2, null]]. Figure 2.10 shows the representation of this structure in terms of pairs.

Figure 2.10

Structure formed 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.12 shows the structure in figure 2.10 viewed as a tree.

Figure 2.12

The list structure in figure 2.10 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(list(1, 2), list(3, 4));

length(x);

count_leaves(x);

list(x, x);

list(list(list(1, 2), 3, 4), list(list(1, 2), 3, 4))

length(list(x, x));

count_leaves(list(x, x));

To implement count_leaves, recall the recursive plan for computing length:

The length of a list x is 1 plus the length of the tail of x.
The length of the empty list is 0.

The function count_leaves is similar. The value for the empty list is the same:

count_leaves of the empty list is 0.

But in the reduction step, where we strip off the head of the list, we must take into account that the head may itself be a tree whose leaves we need to count. Thus, the appropriate reduction step is

count_leaves of a tree x is count_leaves of the head of x plus count_leaves of the tail of x.

Finally, by taking heads we reach actual leaves, so we need another base case:

count_leaves of a leaf is 1.

To aid in writing recursive functions on trees, our JavaScript environment provides the primitive predicate is_pair, which tests whether its argument is a pair. Here is the complete function:

[1]

function count_leaves(x) {
    return is_null(x)
           ? 0
           : ! is_pair(x)
           ? 1
           : count_leaves(head(x)) + count_leaves(tail(x));
}

Exercise 2.24

Suppose we evaluate the expression list(1, list(2, list(3, 4))). Give the result printed by the interpreter, the corresponding box-and-pointer structure, and the interpretation of this as a tree (as in figure 2.12).

[1, [[2, [[3, [4, null]], null]], null]]

Exercise 2.25

Give combinations of heads and tails that will pick 7 from each of the following lists, given in list notation:

list(1, 3, list(5, 7), 9)

list(list(7))

list(1, list(2, list(3, list(4, list(5, list(6, 7))))))

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))))))))))));

Exercise 2.26

Suppose we define x and y to be two lists:

const x = list(1, 2, 3);

const y = list(4, 5, 6);

What is the result of evaluating each of the following expressions, in box notation and list notation?

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]]

Exercise 2.27

Modify your reverse function of exercise 2.18 to produce a deep_reverse function that takes a list as argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well. For example,

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

x;

list(list(1, 2), list(3, 4))

reverse(x);

list(list(3, 4), list(1, 2))

deep_reverse(x);

list(list(4, 3), list(2, 1))

function deep_reverse(items){
    return is_null(items)
           ? null
           : is_pair(items)
           ? append(deep_reverse(tail(items)),
                    pair(deep_reverse(head(items)),
                         null))
           : items;
}

Exercise 2.28

Write a function fringe that takes as argument a tree (represented as a list) and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example,

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

fringe(x);

list(1, 2, 3, 4)

fringe(list(x, x));

list(1, 2, 3, 4, 1, 2, 3, 4)

function fringe(x) {
    return is_null(x)
           ? null
           : is_pair(x)
           ? append(fringe(head(x)), fringe(tail(x)))
           : list(x);
}

Exercise 2.29

A binary mobile consists of two branches, a left branch and a right branch. Each branch is a rod of a certain length, from which hangs either a weight or another binary mobile. We can represent a binary mobile using compound data by constructing it from two branches (for example, using list):

function make_mobile(left, right) {
    return list(left, right);
}

A branch is constructed from a length (which must be a number) together with a structure, which may be either a number (representing a simple weight) or another mobile:

function make_branch(length, structure) {
    return list(length, structure);
}

Write the corresponding selectors left_branch and right_branch, which return the branches of a mobile, and branch_length and branch_structure, which return the components of a branch.
Using your selectors, define a function total_weight that returns the total weight of a mobile.
A mobile is said to be balanced if the torque applied by its top-left branch is equal to that applied by its top-right branch (that is, if the length of the left rod multiplied by the weight hanging from that rod is equal to the corresponding product for the right side) and if each of the submobiles hanging off its branches is balanced. Design a predicate that tests whether a binary mobile is balanced.
Suppose we change the representation of mobiles so that the constructors are

function make_mobile(left, right) {
    return pair(left, right);
}
function make_branch(length, structure) {
    return pair(length, structure);
}

How much do you need to change your programs to convert to the new representation?

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))
        );
}

With this alternative representation, the selector functions for mobile and branch need to change as follows:
この代替表現では、モビールと枝のセレクタ関数を次のように変更する必要があります：
```
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);
}
```

Mapping over trees
ツリーに対するマッピング

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));
}

scale_tree(list(1, list(2, list(3, 4), 5), list(6, 7)),
           10);

list(10, list(20, list(30, 40), 50), list(60, 70))

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.

Exercise 2.30

Declare a function square_tree analogous to the square_list function of exercise 2.21. That is, square_tree should behave as follows:

square_tree(list(1,
                 list(2, list(3, 4), 5),
                 list(6, 7)));

list(1, list(4, list(9, 16), 25), list(36, 49)))

Declare square_tree both directly (i.e., without using any higher-order functions) and also by using map and recursion.

Directly:

function square_tree(tree) {
    return is_null(tree)
           ? null
           : ! is_pair(tree)
           ? square(tree)
           : pair(square_tree(head(tree)),
                  square_tree(tail(tree)));
}

[1, [[4, [[9, [16, null]], [25, null]]], [[36, [49, null]], null]]]

The version using map:

function square_tree(tree) {
    return map(sub_tree => ! is_pair(sub_tree)
                           ? square(sub_tree)
                           : square_tree(sub_tree),
               tree);
}

[1, [[4, [[9, [16, null]], [25, null]]], [[36, [49, null]], null]]]

Exercise 2.31

Abstract your answer to exercise 2.30 to produce a function tree_map with the property that square_tree could be declared as

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);
}

[1, [[4, [[9, [16, null]], [25, null]]], [[36, [49, null]], null]]]

Exercise 2.32

We can represent a set as a list of distinct elements, and we can represent the set of all subsets of the set as a list of lists. For example, if the set is list(1, 2, 3), then the set of all subsets is

list(null, list(3), list(2), list(2, 3),
     list(1), list(1, 3), list(1, 2),
     list(1, 2, 3))

Complete the following declaration of a function that generates the set of subsets of a set and give a clear explanation of why it works:

function subsets(s) { if (is_null(s)) { return list(null); } else { const rest = subsets(tail(s)); return append(rest, map($\langle{}$??$\rangle$, 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));
    }
}

[ null,
  [ [3, null],
    [ [2, null],
      [ [2, [3, null]],
        [ [1, null],
          [ [1, [3, null]],
            [ [1, [2, null]],
              [[1, [2, [3, null]]], null]
            ]
          ]
        ]
      ]
    ]
  ]
]

The argument starts in a similar way as the argument for the function cc in section 1.2.2: A subset either contains the first element $e$ of the given set, or it doesn't. If it doesn't, the problem becomes strictly smaller: Compute all subsets of the tail of the list that represents the given set. If it does, it must result from adding $e$ to a subset that doesn't contain $e$. In the end, we need to append both lists of subsets to obtain the list of all subsets.

Mapping over treesツリーに対するマッピング

Mapping over trees
ツリーに対するマッピング