►zthomae’s SICP solutions
▼3 Chapter 3
3.1 Exercise 3.1
3.2 Exercise 3.2
3.3 Exercise 3.3
3.4 Exercise 3.4
3.5 Exercise 3.5
3.6 Exercise 3.6
3.7 Exercise 3.7
3.8 Exercise 3.8
3.9 Exercise 3.9
3.10 Exercise 3.10
3.11 Exercise 3.11
3.12 Exercise 3.12
3.13 Exercise 3.13
3.14 Exercise 3.14
3.15 Exercise 3.15
3.16 Exercise 3.16
3.17 Exercise 3.17
3.18 Exercise 3.18
3.19 Exercise 3.19
3.20 Exercise 3.20
3.21 Exercise 3.21
3.22 Exercise 3.22
3.23 Exercise 3.23
3.24 Exercise 3.24
3.25 Exercise 3.25
3.26 Exercise 3.26
3.27 Exercise 3.27
3.28 Exercise 3.28
3.29 Exercise 3.29
3.30 Exercise 3.30
3.31 Exercise 3.31
3.32 Exercise 3.32
3.33 Exercise 3.33
3.34 Exercise 3.34
3.35 Exercise 3.35
3.36 Exercise 3.36
3.37 Exercise 3.37
3.38 Exercise 3.38
3.39 Exercise 3.39
3.40 Exercise 3.40
3.41 Exercise 3.41
3.42 Exercise 3.42
3.43 Exercise 3.43
3.44 Exercise 3.44
3.45 Exercise 3.45
3.46 Exercise 3.46
3.47 Exercise 3.47
3.48 Exercise 3.48
3.49 Exercise 3.49
3.50 Exercise 3.50
3.51 Exercise 3.51
3.52 Exercise 3.52
3.53 Exercise 3.53
3.54 Exercise 3.54
3.55 Exercise 3.55
3.56 Exercise 3.56
3.57 Exercise 3.57
3.58 Exercise 3.58
3.59 Exercise 3.59
3.60 Exercise 3.60
3.61 Exercise 3.61
3.62 Exercise 3.62
3.63 Exercise 3.63
3.64 Exercise 3.64
3.65 Exercise 3.65
3.66 Exercise 3.66
3.67 Exercise 3.67
3.68 Exercise 3.68
3.69 Exercise 3.69
3.70 Exercise 3.70
3.71 Exercise 3.71
3.72 Exercise 3.72
3.73 Exercise 3.73
3.74 Exercise 3.74
3.75 Exercise 3.75
3.76 Exercise 3.76
3.77 Exercise 3.77
3.78 Exercise 3.78
3.79 Exercise 3.79
3.80 Exercise 3.80
3.81 Exercise 3.81
3.82 Exercise 3.82
    ← prev  up  next → 

3.14 Exercise 3.14

Consider the procedure below:

(define (mystery x)
  (define (loop x y)
    (if (null? x)
        y
        (let ((temp (cdr x)))
          (set-cdr! x y)
          (loop temp x))))
  (loop x '()))

In general, this procedure will reverse a list (while trashing the list being reversed – more on this later). Consider this brief trace:

Suppose x is the list v, defined as (list ’a ’b ’c ’d). We start by evaluating (loop x ’()). Since x is not nil, we then set aside (cdr x), which is ’(b c d), and set the cdr of x to ’(). The list v is now ’(a). Then we call loop again, as (loop temp x).

Since temp, the new x, is not null, we set aside its cdr and set the cdr to be the list ’(a). The list is now ’(b a). We then call (loop temp x) again.

We continue looping until temp is empty, which will happen after every element of the list has been prepended to the front of the list we are now calling x. This list is then returned. However, the original list is still set to ’(a) – that is, what x was set to in the first loop. x still has the value from the first loop because subsequent calls to loop shadowed it, resulting in the modification of other lists. The only lists we are left with are this shortened version of x and the fully-reversed original list.

It would possibly be more useful to define a procedure that points x to the reversed list. In that way, we could reverse a list in place, with the list taking on the name of its reversed self. However, doing so is fraught with peril. We can’t simply make mystery return (set! x (loop x ’())) because this will only change what the name x points to, not the actual list passed in as a parameter. And using set-car! and set-cdr! to change this list is also dangerous. Suppose we do something like

(let ((reversed (loop x '())))
  (set-car! x (car reversed))
  (set-cdr! x (cdr reversed)))

This looks like it will set x to be the list made up of the components of the reversed list. However, it does not do this. First we set the first element of x to be the first element of the reversed list. However, this also changes the value at the end of the reversed list, making it ’(c b d)! And then setting the rest of x to be the rest of the reversed list, where the last element of the reversed list is actually x, will create a cycle.

TODO: Can we actually solve this?

    ← prev  up  next →