SICP 2.33: List-manipulation operations as accumulations

From SICP section 2.2.3 Sequences as Conventional Interfaces

Section 2.2.3 of SICP introduces the accumulate procedure, which combines elements of a list given an initial value and an operation to combine them with.

(define (accumulate op initial sequence)
   (if (null? sequence)
       initial
       (op (car sequence)
           (accumulate op initial (cdr sequence)))))

> (accumulate + 0 (list 1 2 3 4 5))
15
> (accumulate * 1 (list 1 2 3 4 5))
120

Exercise 2.33 asks us to fill in the missing expressions in the following procedure definitions to implement some basic list-manipulation operations as accumulations.

map

(define (map p sequence)
   (accumulate (lambda (x y) <??>) nil sequence))

The map procedure should accept a procedure and a list as arguments, and it should apply the procedure to each element of that list. We can finish the lambda above by making it apply the procedure p to x, then cons that result to the accumulated sequence.

(define (map p sequence)
   (accumulate (lambda (x y) (cons (p x) y)) null sequence))

Let's also define a couple of simple procedures to test with.

(define (double x)
   (* 2 x))
(define (square x)
   (* x x))

> (map double (list 1 2 3 4 5))
(2 4 6 8 10)
> (map square (list 1 2 3 4 5))
(1 4 9 16 25)

append

(define (append seq1 seq2)
   (accumulate cons <??> <??>))

The append procedure accepts two lists as its parameters and simply appends the second list to the end of the first. My first attempt at this solution was to simply pass the two sequences to accumulate in their original order, but this gives us the wrong output.

(define (append seq1 seq2)
   (accumulate cons seq1 seq2))

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

This is because of the way the accumulate procedure works. Each element of seq2 is being recursively appended to the front of seq1. All we need to do to fix this problem is reverse the order in which the lists are passed to accumulate.

(define (append seq1 seq2)
   (accumulate cons seq2 seq1))

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

length

(define (length sequence)
   (accumulate <??> 0 sequence))

This seems like it should be the easiest one of the bunch. The length procedure should simply return the length of the initial sequence. But accumulate combines each element of a sequence using the operation we pass to it. How do we get it to just return the length of the sequence? We can do that by simply giving it an operation that will ignore each element of the sequence, and just increment the accumulated value.

(define (length sequence)
   (accumulate (lambda (x y) (+ 1 y)) 0 sequence))

> (length (list 2 4 6))
3
> (length (list 9 8 7 6 5))
5

Related:

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

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.

SICP 2.21 - 2.23: Mapping over lists

From SICP section 2.2.1 Representing Sequences

The last few exercises in section 2.2.1 introduce the concept of mapping. The map procedure takes a procedure and a list as arguments, and returns a list of the results produced by applying the procedure to each element in the list.

(define (map proc items)
   (if (null? items)
       null
       (cons (proc (car items))
             (map proc (cdr items)))))

The higher-order procedure map abstracts away the details of traversing a list and allows you to think in terms of procedures that you want to apply to an entire list.


Exercise 2.21 asks us to complete two different implementations of square-list by filling in missing expressions. Each procedure takes a list of numbers as its argument and returns a list of the squares of those numbers. The first example handles list traversal on its own.

(define (square-list items)
   (if (null? items)
       null
       (cons (* (car items) (car items))
             (square-list (cdr items)))))

Note that the structure is identical to that of map. The only difference is that the procedure applied to each element of the list is hard-coded instead of passed in as a parameter.

The second implementation defines square-list in terms of map.

(define (square-list items)
   (map (lambda (x) (* x x)) items))

There's a major difference here. In the second implementation we only need to think about the procedure that we want to apply to each element of the list and map takes care of the rest.

> (square-list (list 1 2 3 4 5))
(1 4 9 16 25)

Exercise 2.22 shows us two attempts at implementing square-list using an iterative process and asks us to explain what's wrong with them.

(define (square-list items)
   (define (iter things answer)
     (if (null? things)
         answer
         (iter (cdr things)
               (cons (square (car things))
                     answer))))
   (iter items null))

This first implementation produces a list in the reverse order of the input list.

> (square-list (list 1 2 3 4 5))
(25 16 9 4 1)

The result is reversed because as the procedure iterates through the list it takes an item from the front of the list, squares it, then puts the square on the front of the answer list. The square of the last item in the original list will be the last item placed at the front of the answer list.

The implementer tried to fix this bug by interchanging the arguments to cons:

(define (square-list items)
   (define (iter things answer)
     (if (null? things)
         answer
         (iter (cdr things)
               (cons answer
                     (square (car things))))))
   (iter items null))

This may seem like a reasonable thing to do, but it produces a very strange looking result.

> (square-list (list 1 2 3 4 5))
(((((() . 1) . 4) . 9) . 16) . 25)

By flipping the arguments to cons, we've made the first argument a list and the second argument an integer. At every step we're combining the list from the previous step with a new integer and wrapping them in a new list. That accounts for the weird looking result. The good news is that the results are in the right order.

A correct iterative implementation would only require a small change.

(define (square-list items)
   (define (iter things answer)
     (if (null? things)
         answer
         (iter (cdr things)
               (append answer
                       (list (square (car things)))))))
   (iter items null))

Here we just use append to add the new squared value to the end of the answer list each time through the loop, just like we saw in the reverse example in exercise 2.18.

> (square-list (list 1 2 3 4 5))
(1 4 9 16 25)

Exercise 2.23 asks us to implement a for-each procedure, which is very similar to map. The for-each procedure takes a procedure and a list as its arguments, but instead of returning a list it just applies the procedure to each element of the list.

(define (for-each proc items)
   (cond ((null? items) #t)
         (else (proc (car items))
               (for-each proc (cdr items)))))

This is nearly the same as the implementation of map that we started out with. The main difference in implementation is that we need to execute two separate statements in sequence in the else clause instead of just one cons statement.

> (for-each (lambda (x) (newline) (display x))
         (list 57 321 88))

57
321
88#t

Related:

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

SICP 2.20: Dotted-tail notation

From SICP section 2.2.1 Representing Sequences

Exercise 2.20 introduces Scheme's dotted-tail notation, which allows procedures like +, *, and list to take arbitrary numbers of arguments. This is known as a variadic function and is supported in many programming languages with different syntax. In Scheme, a parameter list that has a dot before the last parameter name indicates that when the procedure is called, the initial parameters will be treated as normal, but the final parameter's value will be a list of any remaining arguments.

The following examples are given:

(define (f x y . z) <body>)
(define (g . w) <body>)

The procedure f can be called with two or more arguments. The body of the f procedure will refer to its first two parameters as x and y, and any remaining parameters passed to the procedure will be accessible through the list named z. The procedure g can be called with zero or more parameters. Any parameters will be in the list w.

This exercise asks us to use dotted-tail notation to write a procedure same-parity that takes one or more integer parameters and returns a list of all the arguments that have the same even-odd parity as the first argument. For example:

(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)

(same-parity 2 3 4 5 6 7)
(2 4 6)

We'll design a solution that uses an iterative helper procedure similar to the second length example given in section 2.2.1. The helper function will take as its parameters the list of items to iterate through and a variable to store the answer in as we iterate.

(define (same-parity a . z)
   (define (iter items answer)
     (if (null? items)
         answer
         (iter (cdr items)
               (if (= (remainder (car items) 2)
                      (remainder a 2))
                   (append answer (list (car items)))
                   answer))))
   (iter z (list a)))

The same-parity procedure takes a first parameter a, and any remaining parameters are accessed through the list z. Processing the list is delegated to the helper procedure iter. The first thing iter does is check the list to see if it's null. If so we just return the answer. If there are items left to process in the list, iter is called again with the cdr of the list as its first parameter and the answer as its second parameter. If the car of the list has the same even-odd parity as the first argument to same-parity, then it's appended to the answer.

> (same-parity 1 2 3 4 5 6 7)
(1 3 5 7)
> (same-parity 2 3 4 5 6 7)
(2 4 6)

Related:

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

SICP 2.19: Counting Change Revisited

From SICP section 2.2.1 Representing Sequences

Exercise 2.19 asks us to modify the change counting procedure from section 1.2.2 (which we looked at in depth in exercise 1.14). We need to modify the program so that it takes a list of coins to be used instead of having the denominations hard coded as they were originally. The following lists of coins are provided:

(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

We're also provided with the following modified version of the cc procedure:

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))

All that's left for us to do is define the procedures first-denomination, except-first-denomination, and no-more? in terms of primitive list operations. These procedures are very straightforward.

; return true if passed an empty list
(define (no-more? coin-values)
  (if (null? coin-values) true false))

; return all coin values except the first
(define (except-first-denomination coin-values)
  (cdr coin-values))

; return only the first coin value
(define (first-denomination coin-values)
  (car coin-values))

> (cc 100 us-coins)
292
> (cc 100 uk-coins)
104561

Finally, we're asked if the order of the list coin-values affects the answer produced by cc. We can find out quickly enough by experiment.

; reversed list of us coins
(define su-coins (list 1 5 10 25 50))

> (cc 100 us-coins)
292
> (cc 100 su-coins)
292

We can see that the order doesn't matter. This is because the procedure recursively evaluates every sub-list after subtracting the value of the first coin from the target amount. It doesn't matter if that value is the smallest, largest, or even if the values are shuffled.


Related:

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

SICP 2.18: Reversing a List

From SICP section 2.2.1 Representing Sequences

Exercise 2.18 asks us to define a procedure reverse that takes a list as its argument and returns a list with the same elements in reverse order.

We'll be using the append procedure given in the text which takes two lists and appends the second list to the end of the first:

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

We can reverse a list by appending the car of the list to the reverse of the cdr of the list. (See how easy it is to start thinking in Scheme?) In other words, we just move the first item to the end of the list after reversing the remaining items. This means reverse will make a recursive call to itself, so we also need a base case to make the recursion stop. We can just stop when we reach an empty list.

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

Once again, we can test it out with a few example lists from the text.

> (reverse (list 1 2 3 4))
(4 3 2 1)
> (reverse (list 1 4 9 16 25))
(25 16 9 4 1)
> (reverse (list 1 3 5 7))
(7 5 3 1)
> (reverse (list 23 72 149 34))
(34 149 72 23)

Related:

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

SICP 2.17: Last Item in a List

From SICP section 2.2.1 Representing Sequences

Exercise 2.17 asks us to define a procedure last-pair that returns a list that contains only the last element of a given (non-empty) list.

Earlier in SICP section 2.2.1 we saw that a list is represented in Scheme as a chain of pairs.


Our new procedure needs to return a list, so we need to be careful not to simply return the last value in the list, or even the last pair.

There are several correct ways to do this, but here's a recursive solution (based on the length example from the text) that uses the method of "cdring down" the list.

(define (last-pair items)
  (if (null? (cdr items))
      (list (car items))
      (last-pair (cdr items))))

The first line checks to see if the cdr of the list of items passed in is nil. If it is, the second line creates a new list from the car of the items. If not, the last line makes a recursive call to last-pair with the remaining items in the list.

We can verify that it works by testing it with several of the example lists from the chapter.

> (last-pair (list 1 2 3 4))
(4)
> (last-pair (list 1 4 9 16 25))
(25)
> (last-pair (list 1 3 5 7))
(7)
> (last-pair (list 23 72 149 34))
(34)

Related:

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