SICP 2.30 - 2.31: Mapping over trees

From SICP section 2.2.2 Hierarchical Structures

In section 2.2.1 we saw how to build an abstraction called map that allows us to apply a transformation to each element of a list and return a list of results. The next two exercises show us how to do the same with trees. For example, we're given the scale-tree procedure, which takes a numeric factor and a tree whose leaves are numbers as its arguments. This procedure returns a tree of the same shape, but each number is multiplied by the factor.

We're given two implementations of scale-tree. The first traverses the tree in the same manner as used in count-leaves earlier in the text. In this case, when we encounter a leaf node we multiply it by the factor.

(define (scale-tree tree factor)
   (cond ((null? tree) null)
         ((not (pair? tree)) (* tree factor))
         (else (cons (scale-tree (car tree) factor)
                     (scale-tree (cdr tree) factor)))))

The second implementation uses map and treats the tree structure as a sequence of sub-trees. We map over the sequence, and use lambda to define a procedure that scales each sub-tree. We multiply by the factor when a leaf node is reached.

(define (scale-tree tree factor)
   (map (lambda (sub-tree)
          (if (pair? sub-tree)
              (scale-tree sub-tree factor)
              (* sub-tree factor)))
        tree))

Either implementation above will behave as follows:

(scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7))
            10)
(10 (20 (30 40) 50) (60 70))

Exercise 2.30 asks us to define a procedure called square-tree that's directly analogous to the square-list procedure from exercise 2.21. It needs to behave as follows:

(square-tree
  (list 1
        (list 2 (list 3 4) 5)
        (list 6 7)))

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

We're asked to define both a direct implementation (without using any higher-order procedures) and one that uses map. If you use the two implementations of scale-tree above, these can be defined nearly by direct substitution. The only real difference is that instead of multiplying a leaf node by a given factor, you square it.

; direct implementation
(define (square-tree tree)
   (cond ((null? tree) null)
         ((not (pair? tree)) (* tree tree))
         (else (cons (square-tree (car tree))
                     (square-tree (cdr tree))))))

; using map and recursion
(define (square-tree tree)
   (map (lambda (sub-tree)
          (if (pair? sub-tree)
              (square-tree sub-tree)
              (* sub-tree sub-tree)))
        tree))

Use the test case given above to verify that each of these implementations gives you the same result.

> (square-tree
  (list 1
        (list 2 (list 3 4) 5)
        (list 6 7)))
(1 (4 (9 16) 25) (36 49))

Exercise 2.31 asks us to abstract our answer to exercise 2.30 to produce a tree-map procedure that could be used to define square-tree as:

(define (square-tree tree)
    (tree-map square tree))

As you can see from the square-tree definition above, tree-map should take a procedure and a tree and apply the function to each element of the tree structure. The following solution is modeled after the direct solution of exercise 2.30 above.

; exercise 2.31 tree-map
(define (tree-map proc tree)
   (cond ((null? tree) null)
          ((not (pair? tree)) (proc tree))
          (else (cons (tree-map proc (car tree))
                      (tree-map proc (cdr tree))))))

(define (square x)
   (* x x))

(define (square-tree tree)
   (tree-map square tree))

Once again, use the provided test case to verify that the new implementation gives you the correct result.

> (square-tree
  (list 1
        (list 2 (list 3 4) 5)
        (list 6 7)))
(1 (4 (9 16) 25) (36 49))

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.29: Binary Mobiles

From SICP section 2.2.2 Hierarchical Structures

Exercise 2.29 defines a binary mobile as a structure consisting of a left branch and a right branch, each of which is a rod of a certain length, from which hangs either a weight or another binary mobile.



The following constructors are provided, giving us a representation of binary mobiles held together with the list procedure:

(define (make-mobile left right)
   (list left right))

(define (make-branch length structure)
   (list length structure))

Our first task is to 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.

(define (left-branch mobile)
   (car mobile))

(define (right-branch mobile)
   (car (cdr mobile)))

(define (branch-length branch)
   (car branch))

(define (branch-structure branch)
   (car (cdr branch)))

Next we need to define a procedure total-weight that returns the weight of an entire mobile. The total weight of a mobile is just the sum of the left branch and the right branch. The weight of a branch is defined recursively if the branch is itself a mobile, or just returned if the branch holds a single weight.

(define (branch-weight branch)
   (if (pair? (branch-structure branch))
       (total-weight (branch-structure branch))
       (branch-structure branch)))

(define (total-weight mobile)
   (+ (branch-weight (left-branch mobile))
      (branch-weight (right-branch mobile))))

Note how branch-weight and total-weight call each other recursively. The recursion reaches a base case when a weight (leaf node) is encountered.

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 from the right side) and if each of the sub-mobiles hanging off its branches is balanced. Our next task is to design a predicate procedure that tests whether a binary mobile is balanced.

First we'll need a simple procedure for calculating the torque of a branch from the definition above.

(define (branch-torque branch)
   (* (branch-length branch)
      (branch-weight branch)))

Now we can use the same mutual recursion pattern we used to find the total weight of a mobile to write procedures to determine if a mobile and its branches are balanced.

(define (branch-balanced? branch)
   (if (pair? (branch-structure branch))
       (balanced? (branch-structure branch))
       true))

(define (balanced? mobile)
   (and (= (branch-torque (left-branch mobile))
           (branch-torque (right-branch mobile)))
        (branch-balanced? (left-branch mobile))
        (branch-balanced? (right-branch mobile))))

Before we go on to the last step, this would be a good spot to test what we've done so far. The simplest mobile we can make has two branches with simple weights. Let's define two of those (one balanced and one unbalanced) and run a few simple tests.

> (define a (make-mobile (make-branch 2 3) (make-branch 2 3)))
> a
((2 3) (2 3))
> (define b (make-mobile (make-branch 2 3) (make-branch 4 5)))
> b
((2 3) (4 5))
> (total-weight a)
6
> (total-weight b)
8
> (balanced? a)
#t
> (balanced? b)
#f

Now we can create a more complicated mobile by combining the two above.

> (define c (make-mobile (make-branch 5 a) (make-branch 3 b)))
> c
((5 ((2 3) (2 3))) (3 ((2 3) (4 5))))
> (total-weight c)
14
> (balanced? c)
#f

For one last test case, let's try to make a balanced mobile that has mobile a above on a rod of length 10 on the left branch, and a weight of 5 on the right branch. What would the length of the rod on the right need to be in order to balance the entire mobile?




The torque on the left is the total weight of mobile a multiplied by the length, so 6 x 10 gives us a torque of 60. In order to balance the mobile we need the same torque on the right. Since the right side weight is only 5, we'd need a rod of length 60 / 5 = 12 on the right for the mobile to be balanced.

> (define d (make-mobile (make-branch 10 a) (make-branch 12 5)))
> d
((10 ((2 3) (2 3))) (12 5))
> (balanced? d)
#t

Finally, we're asked how much we'd need to change our programs if the original constructors were changed to the following:

(define (make-mobile left right)
   (cons left right))

(define (make-branch length structure)
   (cons length structure))

The only difference is the use of cons to glue the pieces of the mobile and its branches together instead of list. Since only the constructor and accessor procedures know anything about the underlying structure of a mobile, only the accessors would need to change. In this case only the right-branch and branch-structure procedures are affected.

(define (right-branch mobile)
   (cdr mobile))

(define (branch-structure branch)
   (cdr branch))

This is a great benefit of layering abstractions.

You can test out this new implementation using the same mobiles we defined above.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.28: Flattening Nested Lists

From SICP section 2.2.2 Hierarchical Structures

Exercise 2.28 asks us to write a procedure fringe that takes a tree as its argument and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example

(define x (list (list 1 2) (list 3 4)))

(fringe x)
(1 2 3 4)

(fringe (list x x))
(1 2 3 4 1 2 3 4)

This problem is simpler than the one before it because the return value here is just a flat list. That means we can simply traverse the tree and append each node to the result as we encounter it. Once again, we'll be using the append procedure given in the text to build up the result.

(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))

(define (fringe tree)
  (cond ((null? tree) null)
        ((not (pair? tree)) (list tree))
        (else (append (fringe (car tree))
                      (fringe (cdr tree))))))

If the parameter passed to fringe is not a pair, we simply return its value as a list (this will be the case when we reach a leaf node). Otherwise we append the fringe of the first node of the tree to the fringe of the remaining nodes.

Here are the results using the test case given:

> (define x (list (list 1 2) (list 3 4)))
> x
((1 2) (3 4))
> (fringe x)
(1 2 3 4)
> (fringe (list x x))
(1 2 3 4 1 2 3 4)

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

The Chaos Game

In the BLOSSOMS video lecture Fabulous Fractals and Difference Equations, Laura Zager presents the Chaos Game, which follows a few simple rules.

1. Draw an equilateral triangle and label the point red, blue, and green
2. Start at any vertex
3. Roll a die to get the next color (red, blue, or green)
4. Draw a point halfway between the starting point and the vertex determined by the die roll
5. This new "halfway point" becomes the starting point for the next iteration
   
6. Keep repeating the procedure until a pattern emerges

The point of the exercise is to try and predict what pattern will emerge. The lecture continues on to talk about Fibonacci numbers, difference equations (or recurrence relations), bound and unbound trajectories, and the Mandelbrot set before it eventually gets back to the result of the Chaos Game.

It takes quite a few iterations for a pattern to emerge, so this is a perfect problem for setting up a simulation. You'll need Python and the Python Imaging Library (PIL) to run the following code.

from PIL import Image
import random

# calculate the midpoint between two points
def midpoint(p1, p2):
   return ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)

# define the size of the image and a few color constants
# the hieght of an equilateral triangle is sqrt(3)/2 * base
size = 410, 356 # width, height
white = (255, 255, 255)
black = (0, 0, 0)

# set the corner positions of the triangle
blueCorner = (5, 351)
redCorner = (205, 5)
greenCorner = (405, 351)
corners = (redCorner, blueCorner, greenCorner)

triangle = Image.new("RGBA", size, white)

pivot = blueCorner

for i in range(50000):
   randCorner = corners[ random.randint(0, 2) ]
   pivot = midpoint(pivot, randCorner)
   triangle.putpixel(pivot, black)

triangle.save("triangle.gif")

The code above creates a blank Image canvas and puts random pixels on it, but those pixels form a definite pattern. The pixels are selected by picking a random corner of the triangle and calculating the midpoint between that corner and the previous point drawn.


This is called the Sierpinski triangle, a fractal first described by Polish mathematician Wacław Sierpiński.

This isn't the only fractal that can be created by the Chaos Game. A more general set of rules for the Chaos Game are to start at one vertex of a regular polygon, then draw the next point a fraction r of the distance between it and a vertex picked at random. Most combinations of polygons and fractions won't produce a fractal of course, but there are several that do. From Wolfram MathWorld's article on the Chaos Game we find that for a regular pentagon the fractions 1/3 and 3/8 both produce fractals, as does a regular hexagon with the fraction 1/3.

We'd only need to make a few minor changes to the code above, including the midpoint function, the set of vertices, and the range of the random number generator, in order to generate these fractals. Here are the results.

Pentagon fractal (r = 1/3)


Pentagon fractal (r = 3/8)


Hexagon fractal (r = 1/3)