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.