SICP 2.32: Generating Power Sets

From SICP section 2.2.2 Hierarchical Structures

Exercise 2.32 introduces the concept of the "set of all subsets" of a given set, which you may recognize from mathematics as the power set. If we have the set S = {x, y, z}, then the power set of S is:

P(S) = { {}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z} }

There are a couple of details to note:

1. The empty set {} is a member of every power set.
2. The original set {x, y, z} is also a member of its own power set.

In Scheme we can represent a set as a list of distinct elements, and the power set as a list of sets. In this exercise, we're given the following definition of a procedure that generates the power set of a set, and asked to complete it:

(define (subsets s)
   (if (null? s)
       (list nil)
       (let ((rest (subsets (cdr s))))
          (append rest (map <??> rest)))))

If we're given the set (1 2 3), then the finished procedure should return:

(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

If you read the Wikipedia Power set article that I linked to earlier, you'll see that there's a recursive algorithm for calculating power sets (which I'll now quote liberally).

The first step is to define the following operation:


This function takes an element e and a set T, and returns a set with the element e added to each set X in T.

The procedure for generating the power set follows:

If S = {}, the P(S) = {{}} (the set contaning only the empty set) is returned.

Otherwise:

• Let e be any single element of S.
• Let T be the relative complement of {e} in S.
• 

In other words, the power set of the empty set is the set containing the empty set and the power set of any other set is all the subsets of the set containing some specific element and all the subsets of the set not containing that specific element.

This is exactly the same procedure defined in the text. The only part we have to do is finish the initial operation:


The append and map procedures are already doing much of the work for us. We just need to define a function that will add an element e to the set X. The map procedure will apply whatever function we give it to each set in rest (T in the mathematical definition above). We can define that using lambda as follows.

(define (subsets s)
   (if (null? s)
       (list null)
       (let ((rest (subsets (cdr s))))
          (append rest (map (lambda (x) (cons (car s) x))
                            rest)))))

Here we're recursively calling subsets with (cdr s), which will append to that the car of s (which represents e from the mathematical definition) to each subset of (cdr s). The recursion stops when we run out of elements and the empty set is returned.

We can test it out with the example given.

> (subsets (list 1 2 3))
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

Related:

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

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.

SICP 2.27: Reversing Nested Lists

From SICP section 2.2.2 Hierarchical Structures

Exercise 2.27 asks us to modify our reverse procedure from exercise 2.18 to create a deep-reverse procedure that takes a list as its argument and returns the list with its elements reversed and with all sub-lists reversed as well. For example,

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

x
((1 2) (3 4))

(reverse x)
((3 4) (1 2))

(deep-reverse x)
((4 3) (2 1))

Recall that the solution to exercise 2.18 was to reverse a list by appending the car of the list to the reverse of the cdr of the list.

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

(define (reverse items)
  (if (null? items)
      items
      (append (reverse (cdr items)) (list (car items)))))

We need to do something similar here, but we also need to check to see if each element in the list is a list itself, and reverse it if it is. Since lists can be nested as many levels deep as we want, we'll need to make recursive calls to deep-reverse to handle any depth.

(define (deep-reverse items)
  (cond ((null? items) null)
        ((pair? (car items))
         (append (deep-reverse (cdr items))
                 (list (deep-reverse (car items)))))
        (else
         (append (deep-reverse (cdr items))
                 (list (car items))))))

This solution still follows the same basic idea of reverse. We're still appending the car of the list to the reverse of its cdr, but now we first check to see if the car of the list is a pair. If the car is a pair we need to reverse it as well by passing it through deep-reverse. If not, we only need to deep-reverse the cdr.

> (define x (list (list 1 2) (list 3 4)))
> (reverse x)
((3 4) (1 2))
> (deep-reverse x)
((4 3) (2 1))

That test is fine if the nesting is only one level deep, but we should also test our code for lists nested at least one level deeper.

> (define y (list (list 1 2) (list (list 3 4) (list 5 6 7))))
> y
((1 2) ((3 4) (5 6 7)))
> (deep-reverse y)
(((7 6 5) (4 3)) (2 1))

Related:

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

SICP 2.24 - 2.26: Hierarchical Structure Basics

From SICP section 2.2.2 Hierarchical Structures

Section 2.2.2 introduces more complex data structures than the simple lists we've been working with so far. We now start to build lists whose elements are themselves lists. By doing so we create hierarchical data structures. The first few exercises in this section illustrate the basics.

Exercise 2.24 asks us to evaluate the expression (list 1 (list 2 (list 3 4))). We're to show the result printed by the interpreter, the corresponding box-and-pointer-structure, and an interpretation of the resulting structure as a tree.

The expression evaluates as follows:

> (list 1 (list 2 (list 3 4)))
(1 (2 (3 4)))

In somewhat plain English, this is a list whose first element is the number 1 and whose second element is another list. That list has the number 2 as its first element and another list as its second element. This final list has as its elements the numbers 3 and 4.

Here are the box-and-pointer and tree representations of the same structure.







Exercise 2.25 asks us to use combinations of car and cdr to pick the number 7 from each of the following structures:

(1 3 (5 7) 9)

((7))

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

The first thing we should do is figure out how to write an expression that will produce each of these structures. After a little bit of experimentation, we come up with the following:

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

> (list (list 7))
((7))

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

Now that we know how each structure is created, we can experiment with car and cdr to see how we break these structures down.

(1 (2 (3 (4 (5 (6 7))))))
> (car (list 1 3 (list 5 7) 9))
1
> (cdr (list 1 3 (list 5 7) 9))
(3 (5 7) 9)

A bit more probing along these lines reveals the answer for the first structure.

> (cdr (cdr (list 1 3 (list 5 7) 9)))
((5 7) 9)
> (car (cdr (cdr (list 1 3 (list 5 7) 9))))
(5 7)
> (cdr (car (cdr (cdr (list 1 3 (list 5 7) 9)))))
(7)
> (car (cdr (car (cdr (cdr (list 1 3 (list 5 7) 9))))))
7

If that last step is confusing, just remember that list gives us a sequence of pairs formed by nested calls to cons, so (list 5 7) is equivalent to (cons 5 (cons 7 null)). We need to use car to get the first value from the pair returned in the next-to-last step.

The second structure is rather straightforward and so is its solution.

> (car (car (list (list 7))))
7

The last solution is similar to the first, but a little bit more complicated. Here's the solution:

> (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr
    (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7))))))))))))))))))
7

If you were expecting to be able to simply "cdr-down" this structure without all those calls to car, once again, remember that list returns a sequence of pairs. We have to use car to extract the inner list returned by cdr at each step.

> (cdr (list 5 (list 6 7)))
((6 7))
> (car (cdr (list 5 (list 6 7))))
(6 7)

Exercise 2.26 simply asks us to consider the following two lists:

(define x (list 1 2 3))
(define y (list 4 5 6))

We're then asked what is printed in the interpreter in response to evaluating each of the following expressions:

(append x y)

(cons x y)

(list x y)

These are the three procedures for combining expressions that we've learned. Analyzing the results of each function will allow us to review how they differ from each other.

> (define x (list 1 2 3))
> (define y (list 4 5 6))

> (append x y)
(1 2 3 4 5 6)
> (cons x y)
((1 2 3) 4 5 6)
> (list x y)
((1 2 3) (4 5 6))

The append procedure takes the elements from two lists and produces a new list. When given two lists as parameters, the cons procedure returns a list whose first element is the first parameter list and whose remaining elements are the elements of the second list (we saw this at the beginning of section 2.2.1 Representing Sequences). Finally the list procedure simply wraps its parameters in a new list without doing any merge or append operations on them. The returned list just has two lists as its elements.


Related:

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