## Simply Scheme Chapter 18 – Trees

This is more of a quote-and-commentary-heavy chapter for me as there are relatively few problems. The headings don’t necessarily correspond to sections within the chapter.

## Trees

The big advantage of full-featured lists over sentences is their ability to represent structure in our data by means of sublists. In this chapter we’ll look at examples in which we use lists and sublists to represent two-dimensional information structures. The kinds of structures we’ll consider are called trees because they resemble trees in nature:

The components of a tree are called nodes. At the top is the root node of the tree; in the interior of the diagram there are branch nodes; at the bottom are the leaf nodes, from which no further branches extend.

[…]

We say that every node has a datum and zero or more children. For the moment, let’s just say that the datum can be either a word or a sentence. The children, if any, are themselves trees. Notice that this definition is recursive-a tree is made up of trees. (What’s the base case?)

Base case would be a node with no children, I think.

This family metaphor is also part of the terminology of trees.[1] We say that a node is the parent of another node, or that two nodes are siblings.

## Mutual Recursion

The book presents this procedure:

And then proceeds to offer an alternative:

In Chapter 14 we wrote recursive procedures that were equivalent to using higher-order functions. Let’s do the same for `count-leaves`.

Note that `count-leaves` calls `count-leaves-in-forest`, and `count-leaves-in-forest` calls `count-leaves`. This pattern is called mutual recursion.

In this example of mutual recursion, `count-leaves` is the program that actually checks whether a specific element of the tree is a leaf, and returns the “1” value if so. If not, it then invokes `count-leaves-in-forest` to return the list of any children. `count-leaves-in-forest` returns 0 for a `forest` that returns null – that is, if the forest is empty (there are no children). Otherwise it adds the sum of `count-leaves` invoked with argument `car forest` and `count-leaves-in-forest` invoked with argument `cdr forest`.

Short summary: `count-leaves-in-forest` navigates through the tree list with `car` and `cdr` and `count-leaves` returns the 1 for actual leaves and invokes `count-leaves-in-forest` for non-leaves.

Mutual recursion is often a useful technique for dealing with trees. In the typical recursion we’ve seen before this chapter, we’ve moved sequentially through a list or sentence, with each recursive call taking us one step to the right. In the following paragraphs we present three different models to help you think about how the shape of a tree gives rise to a mutual recursion.

In the first model, we’re going to think of `count-leaves` as an initialization procedure, and `count-leaves-in-forest` as its helper procedure. Suppose we want to count the leaves of a tree. Unless the argument is a very shallow[2] tree, this will involve counting the leaves of all of the children of that tree. What we want is a straightforward sequential recursion over the list of children. But we’re given the wrong argument: the tree itself, not its list of children. So we need an initialization procedure, `count-leaves`, whose job is to extract the list of children and invoke a helper procedure, `count-leaves-in-forest`, with that list as argument.

Ah, so the invocation of the `children` procedure causes `count-leaves` to be the initialization procedure in this model.

The helper procedure follows the usual sequential list pattern: Do something to the `car` of the list, and recursively handle the `cdr` of the list. Now, what do we have to do to the `car`? In the usual sequential recursion, the `car` of the list is something simple, such as a word. What’s special about trees is that here the `car` is itself a tree, just like the entire data structure we started with.

To concretize, in the lengthy `world-tree` example they use in the chapter, `world-tree` is a tree with many children, but `car (children world-tree)` is likewise a tree with children.

Here’s `world-tree`:

And here are procedures operating on `world-tree`

Therefore, we must invoke a procedure whose domain is trees: `count-leaves`.

That makes sense.

This model is built on two ideas. One is the idea of the domain of a function; the reason we need two procedures is that we need one that takes a tree as its argument and one that takes a list of trees as its argument.

A tree includes its own datum plus the list of children. So we need one procedure for handling the whole tree structure and one procedure for handling just the list of children.

The other idea is the leap of faith; we assume that the invocation of `count-leaves` within `count-leaves-in-forest` will correctly handle each child without tracing the exact sequence of events.

The second model is easier to state but less rigorous. Because of the two-dimensional nature of trees, in order to visit every node we have to be able to move in two different directions. From a given node we have to be able to move down to its children, but from each child we must be able to move across to its next sibling.
The job of `count-leaves-in-forest` is to move from left to right through a list of children. (It does this using the more familiar kind of recursion, in which it invokes itself directly.) The downward motion happens in `count-leaves`, which moves down one level by invoking `children`. How does the program move down more than one level? At each level, `count-leaves` is invoked recursively from `count-leaves-in-forest`.

This model is the one that most easily fits my existing thinking/intuitions. I often like to think of what programs do in somewhat mechanical terms like “moving through” some set of data.

The third model is also based on the two-dimensional nature of trees. Imagine for a moment that each node in the tree has at most one child. In that case, `count-leaves` could move from the root down to the single leaf with a structure very similar to the actual procedure, but carrying out a sequential recursion:

The trouble with this, of course, is that at each downward step there isn’t a single “next” node. Instead of a single path from the root to the leaf, there are multiple paths from the root to many leaves. To make our idea of downward motion through sequential recursion work in a real tree, at each level we must “clone” `count-leaves` as many times as there are children. `Count-leaves-in-forest` is the factory that manufactures the clones. It hires one `count-leaves` little person for each child and accumulates their results.

And in the earlier version of `count-leaves` that used `(reduce + (map count-leaves (children tree)))))`, it was the `map` function that was the factory which manufactured the clones.

## Dealing with Trees

The following procedure figures out whether a datum is in a tree:

But the book describes it as inefficient, because it performs unnecessary computations even after it find the `place` being looked for. So they propose this rewrite:

More mutual recursion. `in-tree?` has the domain of trees, and `in-forest?` has the domain of a list of trees.

The `or` structure in `in-tree?` means that `in-tree?` will return true either if `datum tree` is `equal?` to `place` or if `place` is somewhere else in the forest.

Although any mutual recursion is a little tricky to read, the structure of this program does fit the way we’d describe the algorithm in English. A place is in a tree if one of two conditions holds: the place is the datum at the root of the tree, or the place is (recursively) in one of the child trees of this tree. That’s what `in-tree?` says. As for `in-forest?`, it says that a place is in one of a group of trees if the place is in the first tree, or if it’s in one of the remaining trees.

The next thing the book wants to be able to do is `locate`:

This is more complex than `in-tree?` because we want to say where a value is, not just say whether it exists somewhere.

The algorithm is recursive: To look for Berkeley within the world, we need to be able to look for Berkeley within any subtree. The `world` node has several children (countries). `Locate` recursively asks each of those children to find a path to Berkeley. All but one of the children return `#f`, because they can’t find Berkeley within their territory. But the `(united states)` node returns

To make a complete path, we just prepend the name of the current node, `world`, to this path. What happens when `locate` tries to look for Berkeley in Australia? Since all of Australia’s children return `#f`, there is no path to Berkeley from Australia, so `locate` returns `#f`.

`locate` first checks if the `city` is equal to the `datum` of `tree`. If so, it calls `list` on `city` (this makes sense later). Otherwise, it defines a `let` called `subpath` using `locate-in-forest` and the arguments `city` and `children tree`. `subpath` will only return true if a valid subpath exists. If it does, `cons` will create a list from `datum tree` and `subpath`.

If a subpath doesn’t exist, the procedure will return false.

Let’s walk through this procedure looking for ‘berkeley in the `world-tree`. I’m truncating the output of `trace` here cuz it’s quite long. First `locate` checks if `berkeley` is equal to `world`.

It isn’t, so then `locate-in-forest` runs with `berkeley`.

The procedures try to find Berkeley in Italy first, since that’s the first country in the world-tree, but do not meet with success.

Then the procedures get to the US. First `locate` checks whether the `united states` is equal to `berkeley`. This is not the case.

The procedures start to drill down and ultimately find a match

I wanted a more detailed view of what was going on in this procedure, and in particular how the stuff got appended together.

I discovered Scheme’s `begin` procedure. The utility of `begin` for debugging is described here.

Here’s my reworked `locate`:

So `locate` arrives at `berkeley`. Since `city` is equal to `(datum tree)`, we run `list city`, returning `'(berkeley)`.

Now, for the call `(locate 'berkeley '(california (berkeley) ((san francisco)) (gilroy)))`, we know what the subpath is – `(berkeley)`. So we `cons` `california` with `'(berkeley)`.

This general pattern repeats as we percolate back up the tree of calls

using `(list (datum tree) subpath))` would not get us the output we want, btw:

## Abstract Data Types

These procedures:

define an abstract data type for trees, wherein “a tree is a list whose first element is the datum and whose remaining elements are subtrees.”

The book notes that you can deal with nodes by using `car` and `cdr` but using the ADT-specific selectors helps program readability. This is a good point – you should use your abstractions, not fight them by using lower-level stuff.

## Getting Unstuck ๐ค

Having some trouble with this chapter. This section reflects my efforts at getting unstuck:

### Domain, range, and purpose of procedures dealing with treees and world-tree

#### General tree procedures

##### make-node

• domain: a word or list as the first argument and a list as the second argument. (You can give `make-node` a word as the second argument but then you will get the “dot” output described in an earlier chapter.)
• range: a list whose `car` is the first argument and whose `cdr` is the second argument.
• intended use within Tree abstract data type: combine a word or list representing the name of a place (e.g. `'world`, `'(united states)`) with a list of children of the place. If there is a higher level entity above the level of entity upon which `make-node` is being invoked, the invocations of `make-node` should be enclosed in an invocation of `list`, as in the following example:
##### datum

• domain: a list
• range: the `car` of that list, which may be a word or a list
• intended use within Tree abstract data type: get the first element of a list, representing the “label” of a particular node.
• Note that nodes return within nested lists when using the `children` procedure, so you need to do `datum (car (children tree)))` to get the datum of a child tree. For example, consider the italy-tree I made:

If we want to return “italy”, we need to do `(datum (car (children italy-tree)))`:

If we just do `(datum (children italy-tree))`, which is what I tried initially, this happens:

This is because the entirety of `(italy (venezia) (riomaggiore) (firenze) (roma))` returns within a nested list when `children` is invoked on `italy-tree` (keep in mind that `'world` was the root node within `italy-tree`):

If we want to be able to get at just `'italy` by itself, we need to invoke `car` on this nested list so we can get the list that `datum` can address:

##### children

• domain: takes a list with more than one element as an argument
• range: returns the `cdr` of the list as a list
• intended use within Tree abstract data type: return the children of a given node.
• Example:

#### world-tree specific procedures

##### cities

• domain: a list.
• range: a list containing the elements of the list provided as an argument to the procedure.
• intended use within `world-tree`: takes the `leaf` procedure and applies it to a list containing the names of cities, which, in the context of the `world-tree`, will always be the leaves. This is a bit neater than having to apply `make-node` on a bunch of individual cities and then group them together in a list.
##### leaf

• domain: words, lists, numbers, booleans
• range: a list with the argument provided as the only element within that list.
• intended use within `world-tree`: the procedure invokes `make-node` with the argument provided to `leaf` as the first argument and with an empty list as the second argument (which represents the children within `make-node`). This creates a list with no children, or a leaf. Thus this procedure is designed to create nodes with no children.

### Analyze the procedures involved in the infix expression parser in detail

`parse` is initially invoked with the expression you are trying to parse.

This initializing procedure calls `parse-helper` with the initial expression and two empty lists representing the operators (meaning the arithmetic operators) and operands (meaning the numbers) respectively.

Within the first `cond` of `parse-helper`, we check whether the `expr` is `null?` in the predicate. If so, we evaluate a somewhat complex consequent which has an `if` statement. If the `operators` expression (the second argument passed into `parse-helper`) is also `null?`, we return the `car` of the operands list. Otherwise (meaning, if at least one operator remains) we pass an empty list representing the empty expression along with the operators and operands to `handle-op`.

If the first value of `car expr` is a number, we recursively call `parse-helper` with the `cdr` of `expr`, the current list of operators, and a longer expression. The longer expression consists of the `cons` of the following two expressions:
1. the result of invoking `make-node` with `car expr` and an empty list, which creates a node (in our tree abstract data type, which is represented by a list in Scheme) with the first number of the `expr` as the root, and
2. the existing `operands` list

I believe the process described in this `cond` is reflected in the following image – the procedure detects a number as the leading value of the `expr` and then adds that number to the operands list as a node/list:

The next `cond` clause checks if the `car` of `expr` is a list. This is necessary because we can have nested parenthetical expressions within our infix expression. If `car expr` is a list, then we recursively call `parse-helper` with `cdr expr`, operators, and a longer expression. The longer expression consists of the `cons` of:
1. the result of a call to `parse` with `car expr` as the argument, and
2. the list of operands.

The call to `parse` is to break down our sublist into a form we can use. It’s worth keeping in mind that the “operands” list is essentially also the “fully processed tree” list. We keep operations and operands list temporarily in order to deal with the issue of sometimes needing to wait until an expression is definitely “finished” before processing it, but ultimately the `parse` program is trying to construct a complete tree, with operators and operands, in the “operands” list. That’s why we’re only `cons`‘ing the results of the call to parse with `operands` and why that’s fine – because after the call to `parse` is finished with the sublist, we want the result of that internal processing in `operands`.

The `else` clause is the most complicated part of `parse-helper`.

I’m going to briefly describe `precedence` since it’s relevant:

If the operator passed into `precedence` appears in the list `'(+ -)`, then return 1. Otherwise, return 2.

Back to the `else` clause. If either one of two conditions is met, we recursively call `parse-helper` with `cdr expr`, the `cons` of `car expr` and `operators`, and `operands`, respectively, as the arguments.

What are the two conditions?
1. If `operators` is `null?`, or
2. If the `precedence` of `car expr` is higher than that of `car operators`.

The second condition represents the case where the next expression in a list has higher precedence than the previous expression, as seen in the book example here:

Infix has implicit grouping based on the operation being performed (cuz of the Order of Operations).
When one operator has lower precedence than another one, that’s an indicator that the previous operation reflects a “complete” substatement. For example:

`(4 * 3 + 2)`
When we get to the `+`, we can be confident that the `4 * 3` represents a completed statement. Why? Because `*` represents an implicit grouping. With the above example the grouping is:

`((4 * 3) + 2)`.

So in that context, the `+` becomes a bit like a close-parentheses indicator. If you had another operator of the same precedent, it wouldn’t be a close-parentheses indicator. E.g.:
`(4 * 3 / 2)`
The above expression has no implied hierarchy of precedence that you need to translate the expression into by adding parentheses – you should perform the operations from left to right, cuz `*` and `/` have the same precedence.

All that said, because `*` is higher precedence and not lower precedence than `+`, we have to add it to the list of operators.

So that takes care of the part of else that deals with precedence. What about the part that deals with when `operators` is `null?`?

So keep in mind the previous `cond` clauses dealt with the cases where:
1. `expr` was null
2. `car expr` was a number
3. `car expr` was a list.

If we assume that infix expressions will consist of nothing but numbers, operators, and numbers, and we know that 1) `expr` isn’t empty, 2) `car expr` isn’t a number or list, then the first value in `expr` must be an operator.
The purpose of our whole `parse` program is to put infix expressions into a structured tree. To do that, we need at least two operands (numbers) and an operator. If we know that there are more values remaining in `expr`, and that `car expr` isn’t a number or list, and that `operands` is empty, then we know that we need to grab that first value from `expr` and add it to `operators`.

If, on the other hand, and given that the previous `cond` clauses have not evaluated to true, we know that 1) the operators list has an entry, and 2) the precedence of `car expr` is not higher than that of `car operators`, then we know we need to “handle” the `car operators` operator and put it in a tree:

How does `handle-op` work?

`handle-op` calls `parse-helper` with `expr` as its first argument, the `cdr` of `operators` as its second argument, and a rather long argument as its third argument. This third argument consists of the `cons` of:
1. the result of calling `make-node` with `car operators` as the first argument and `list (cadr operands) (car operands)` as the second argument. This creates a tree structure with the first element of `operators` as the root of the tree, the second value of `operands` as the first element within the child of that tree, and the first element of `operands` as the second element within the child of that tree.
2. the `cddr` of the operands (representing the third element onward, the first two elements already having been assigned roles within the structure of a tree in the previous step)

This diagram illustrates the general flow of `parse-helper`. The main point is to show how many recursive calls there are.

## Exercises

### โ 18.1

What does
`((SAN FRANCISCO))`
mean in the printout of `world-tree`? Why two sets of parentheses?

I think one set of parentheses is to group the two words of “san francisco” together.
I think another set of parentheses is to indicate that “san francisco” is a node within the world tree.
All nodes have a set of parentheses around them, to indicate that they are nodes within our tree abstract data type. See Great Britain for example:

There are obviously the inner parentheses, but the first paren on the left is a “node” parentheses, which corresponds to the parentheses on the far right which I’ve highlighted. If Great Britain were a leaf node, these parentheses would be all that there was on the line besides the datum of Great Britain itself, and so it’d just be `((great britain))`. Because Great Britain has children, however, the two sets of parentheses are a bit harder to see.
This is not the case with `((san francisco))`, which is a leaf node, and thus has the two sets of parentheses right around it.

### โ 18.2

Suppose we change the definition of the tree constructor so that it uses `list` instead of `cons`:

How do we have to change the selectors so that everything still works?

When I tried to run `locate 'berkeley world-tree` after this change, it failed:

After making the following change to `children`, `locate` worked properly:

Likewise, `count-leaves` failed initially after making the change to `make-node` but worked after making the change to `children` above.

I also tried stuff like this:

It failed after making the change to `make-node` but succeeded after making my change to `children`.

Answer: If we used list instead of cons then we would have a list that two elements; a word and a list.
Cons: `'(australia (wa (perth)) (nsw))`
List: `'(australia ((wa ((perth))) (nsw)))`
For things to still work, we’d need to use cadr, or perhaps `(datum (children x))`.

I found this a bit unclear. It doesn’t say what specific selector you should use `cadr` for. Although since I did use `cadr` in my change to `children`, it is at least potentially compatible with mine.

I also checked this page but the changes suggested did not seem to work.

### โ 18.3

Write `depth,` a procedure that takes a tree as argument and returns the largest number of nodes connected through parent-child links. That is, a leaf node has depth 1; a tree in which all the children of the root node are leaves has depth 2. Our world tree has depth 4 (because the longest path from the root to a leaf is, for example, world, country, state, city).

I was stuck on this one for quite a while. I finally gave up and looked at buntine’s solution. He said this one took him forever so I don’t feel so bad!

Alright so he uses mutual recursion.

First, in `depth`, he checks if a tree is a leaf. If so he returns 1. If not he calls `find-depth` with the entire `tree` and 1. The arguments passed to `find-depth` indicate to me that `depth` is just an “initializer” procedure and `find-depth` is going to be part of a pair of recursive procedures.

Within `find-depth`, the current depth `d` is `cons`‘ed together with a call to `find-depth-in-forest` with the arguments `children tree` and `(+ 1 d`). The values returned from this are passed in as arguments to `max` using `apply.`

For `find-depth-in-forest`, we return the empty list if the tree is null. Otherwise, we `cons` together a call to `find-depth` with `car tree` as first argument and `find-depth-in-forest` with `cdr tree` as the first argument. For both these arguments, `d` is the second argument. Therefore, the `d` only gets incremented once in `find-depth`. I think this makes sense according to the models described in the chapter because `find-depth` is the procedure traveling “vertically” within the tree.

### โ 18.4

Write `count-nodes`, a procedure that takes a tree as argument and returns the total number of nodes in the tree. (Earlier we counted the number of leaf nodes.)

For reference, the world-tree has 44 nodes.

I started with the `count-leaves` procedure as a model:

My thinking was that basically we want to do `count-leaves` but a bit more. In other words, we want to count the leaves but also something else.

In coming up with my solution, I initially started trying to work with the world-tree but ultimately decided that was too big. I made a smaller `italy-tree` of my own to play around with, just to test my solutions with a smaller set of data.

I came up with this as my answer:

This is extremely similar to `count-leaves`. We are still counting all the leaves, which remain the base case. The difference now is that for each non-leaf, we are adding a 1. This simple change causes us to count all the nodes instead of just the leaf nodes.

buntineย solved this with mutual recursion rather than using `map`. You can see that is main procedure is very similar to mine.

### โ 18.5

Write `prune`, a procedure that takes a tree as argument and returns a copy of the tree, but with all the leaf nodes of the original tree removed. (If the argument to `prune` is a one-node tree, in which the root node has no children, then `prune` should return `#f` because the result of removing the root node wouldn’t be a tree.)

I made `not-null?` to help with using `filter`.

To comply with the desired output for a one-node tree, I put a check in the initializer procedure `prune` for whether or not a tree was a leaf. Here’s me running a test for that using a single node `world-only` tree:

Within `prune-tree`, we return an empty list when a tree is a leaf and otherwise we `cons` together the `datum` of the tree with a call to `prune-forest` with argument `children tree`.

Within `prune-forest`, we return the empty list if the forest is null. Otherwise, we `cons` together the results of a call to `prune-tree` with `car forest` and a call to `prune-forest` with `cdr forest`. We also filter the results of these calls with `not-null?`. This cleans up the tree that is generated and prevents it from having a ton of empty lists where the leaves used to be.

world-tree versus pruned world-tree

#### buntine’s solution

buntine has a cool solution:

My solution does not use the filter operator. Instead if the node is leaf then it just skips over it.
Also I prefer using make-node instead of cons for data encapsulation.

I think the key line he’s talking about re: skipping over a leaf is `((leaf? (car forest)) (prune-forest (cdr forest)))`. Nice solution!

### โ 18.6

Write a program `parse-scheme` that parses a Scheme arithmetic expression into the same kind of tree that `parse` produces for infix expressions. Assume that all procedure invocations in the Scheme expression have two arguments.
The resulting tree should be a valid argument to `compute`:

(You can solve this problem without the restriction to two-argument invocations if you rewrite `compute` so that it doesn’t assume every branch node has two children.)

Giving myself no credit here cuz my solution basically reimplemented the existing `parse` procedure and was super inelegant.

`parse-scheme` has to be able to handle the following cases:

1. The expression is empty. At this point we’ll be returning our tree.
2. The next value in the expression is an operator. We probably want to make a new tree node here using the operator.
3. The next value in the expression is a list. We’ll probably do a recursive call here.
4. Otherwise, the next value in the expression is a number.

We don’t have to worry about implicit precedence rules with `parse-scheme` because all the groupings will be explicit. This makes things easier.

Interestingly, the existing `parse` program seems to handle scheme notation just fine:

So the extremely lazy solution to this question would be something like:

๐

Let’s be more serious though. Suppose we have the expression `(* (+ 4 3) 2))`. What would we want `parse-scheme` to do with it?

Well we want it to see that the first value of the expression is `*`, an operator. If we don’t want to look for operators specifically, we can put this in the `else` clause as in the original procedure.
Do we want to immediately make a tree using the operator and the next two elements in the expression? No, because as we see in this example, sometimes the next expression might be a sublist. We don’t want to just dump that sublist into our new tree without any processing. So we’ll take our operator and add it to a list of operators, and then make a recursive call to `parse-scheme-helper` with that operator added to the operator list, and with all but the operator we just added to our list of operators as the value for `expr`:

(some of this code will be placeholder stuff that I will change as I go along)

We also need to be able to handle numbers. We’ll do so in the same way as in the original procedure:

If we get to the end of an expression, and there are any operators left, we want to “handle” those.

Here’s an unfinished procedure:

It can handle something easy, like `(+ 4 3)`:

Can’t handle nested expressions though.

So let’s make it handle those.

I realized I should make a version of `handle-op` that actually calls `parse-scheme-helper` and not `parse-helper`:

After some more steps and trial and error, I came up with this:

It re-implements a lot of the existing `parse` procedure but with some notable differences. The order of checking is a bit different, and it doesn’t have the precedence-checking stuff.

#### buntine’s solution

This is buntine’s solution:

Ah this is so elegant! ๐

For some reason I didn’t consider just making a straight up normal single recursive procedure…

So going through this in detail:

1. check if the `expr` is `null?`. if so, return an empty list.
2. check if `car expr` is a number. if so, `cons` together `leaf (car expr)` (turning the number into a leaf node) and the result of a recursive invocation of `parse-scheme` with `cdr expr` (which takes us to the next item in the list).
3. check if `car expr` is a list. If so, `cons` together the results of a) a recursive invocation of `parse-scheme` with that list as an argument and b) a recursive invocation of `parse-scheme` with `cdr expr`.
4. Otherwise (meaning if `car expr` is an operator) invoke `make-node` with `car expr` as the first argument to `make-node`. The second argument to `make-node` will be a recursive invocation to `parse-scheme` with `cdr expr` as the argument.