# SICP section 1.3 - formulating abstractions with higher-order procedures

## Selected exercises

## Exercise 1.32

The generalised form of `sum`

and `product`

can be defined (recursively) as follows:

```
(define (accumulate combiner null-value term a next b)
(if (> a b)
null-value
(combiner (term a)
(accumulate combiner null-value term (next a) next b))))
```

Redefining `sum`

and `product`

using `accumulate`

:

```
(define (sum term a next b)
(accumulate + 0 term a next b))
(define (product term a next b)
(accumulate * 1 term a next b))
```

The iterative version of `accumulate`

uses an internal procedure with two state variables - one tracks the value of \(a\); the other accumulates the result, which is returned when the terminating condition \(a > b\) is met.

```
(define (accumulate-iter combiner null-value term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (combiner result (term a)))))
(iter a null-value))
```

## Exercise 1.33

`filtered-accumulate`

is a generalised version of `accumulate`

that only combines terms that satisfy a given condition. Its implementation is similar to `accumulate`

, with an added conditional.

```
(define (filtered-accumulate combiner null-value term a next b filter)
(define (next-fa)
(filtered-accumulate combiner null-value term (next a) next b filter))
(if (> a b)
null-value
(if (filter a)
(combiner (term a)
(next-fa))
(next-fa))))
```

Using `filtered-accumulate`

to define a procedure that computes the sum of the squares of prime numbers:

```
(define (sum-square-prime a b)
(filtered-accumulate + 0 square a inc b prime?))
```

…and a procedure that computes the product of integers less than \(n\) that are relatively prime to \(n\):

```
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
(define (identity n) n)
(define (product-rel-prime n)
(define (rel-prime? a)
(= (gcd a n) 1))
(filtered-accumulate * 1 identity 1 inc (- n 1) rel-prime?))
```

## Exercise 1.34

Attempting to evaluate `(f f)`

produces the following error:

```
mit-scheme : The object 2 is not applicable.
dr-racket : application: not a procedure;
expected a procedure that can be applied to arguments
given: 2
arguments...:
```

We can use the substitution model to get a clearer picture of the error:

```
(define (f g) (g 2))
(f f)
(f 2)
(2 2)
```

The second invocation of `f`

attempts to apply \(2\), which is not a procedure, to \(2\). No bueno.

## Exercise 1.37

For this exercise, I found that rewriting the *k-term finite continued fraction* as a single line helped me see more clearly how to implement it as a recursive process:

```
(define (cont-frac n d k)
(define (frac x)
(if (= x k)
(/ (n x) (d x))
(/ (n x) (+ (d x) (frac (+ x 1))))))
(frac 1))
```

To obtain an approximation of \(1/φ\) accurate to 4 decimal places, \(k = 10\).

```
(cont-frac (lambda (i) 1.0)
(lambda (i) 1.0)
10)
```

The iterative version of `cont-frac`

decrements a counter \(x\) that begins with \(k\), accumulates the result in \(acc\), and returns the result when \(x = 0\):

```
(define (cont-frac-iter n d k)
(define (frac x acc)
(if (= x 0)
acc
(frac (- x 1) (/ (n k) (+ (d k) acc)))))
(frac k 0))
```

## Exercise 1.38

For this fraction, we know that all values of \(N_i\) are \(1\). \(D_i\) however, is slightly less straightforward. The (convoluted) pattern I derived from the \(D_i\) series is \(2(i + 1)/3\) if \((i + 1) \bmod 3 = 0\), for all \(i > 1\).

```
(define (d i)
(cond ((= i 1) 1)
((not (= (remainder (+ i 1) 3) 0)) 1)
(else (/ (* 2 (+ i 1)) 3))))
(+ (cont-frac (lambda (i) 1.0)
d
10)
2)
```

## Exercise 1.39

Fairly obvious patterns in both series: \(N_i = -x^2\) for \(i > 1\), and \(D_i = 2i - 1\).

```
(define (tan-cf x k)
(define (n k) (if (= k 1) x (- (square x))))
(define (d k) (- (* 2.0 k) 1))
(cont-frac n d k))
```

## Exercise 1.41

`double`

can be defined as follows:

```
(define (double f)
(lambda (x) (f (f x))))
```

Applying the substitution model shows us that the procedure makes \(2^4\) `inc`

calls, which gives us the answer \(5 + 16 = 21\).

```
(((double (double double)) inc) 5)
(((double (lambda (x) (double (double x)))) inc) 5)
(((lambda (x) (double (double (double (double x))))) inc) 5)
((double (double (double (double inc)))) 5)
((double (double (double (lambda (x) (inc (inc x)))))) 5)
... ; Expands to 16 `inc` calls
21
```

## Exercise 1.42

Procedure composition!

```
(define (compose f g)
(lambda (x) (f (g x))))
```

## Exercise 1.43

Using `compose`

from the previous exercise:

```
(define (repeated f n)
(if (= n 1)
(lambda (x) (f x))
(compose (repeated f (- n 1)) f)))
```

## Exercise 1.44

…and using `repeated`

from the previous exercise:

```
(define dx 0.00001)
(define (smooth f)
(lambda (x) (/ (+ (f (- x dx))
(f x)
(f (+ x dx)))
3.0)))
(define (n-fold-smooth f n x)
((repeated (smooth f) n) x))
```

## Exercise 1.45

Analysis:

```
Root | Damps
2 | 1
3 | 1
4 | 2
5 | 2
6 | 2
7 | 2
8 | 3
9 | 3
10 | 3
11 | 3
12 | 3
13 | 3
14 | 3
15 | 3
16 | 4
```

From this table, we can determine that \(average\_damps = log_2 (root)\), rounded down to the nearest integer.

Scheme does not have a `log`

procedure that allows us to specify a base. To get around this, we can use the log change-of-base formula: \(log_b n = log_a n / log_a b\).

```
(define (average x y) (/ (+ x y) 2.0))
(define (average-damp f)
(lambda (x) (average x (f x))))
(define (expt b n)
(if (= n 0)
1
(* b (expt b (- n 1)))))
(define (log-b2 n)
(/ (log n) (log 2)))
(define (nth-root x n)
(fixed-point ((repeated average-damp (inexact->exact (floor (log-b2 n))))
(lambda (y) (/ x (expt y (- n 1)))))
1.0))
```

## Exercise 1.46

As specified in the exercise, the procedure that `iterative-improve`

should return is one that keeps improving the guess until it is good enough, indicating that it needs to be a procedure that repeatedly calls itself.

For a procedure to call itself, it needs a name - which is why we define an internal procedure and return it. If there is a way to solve this exercise using a `lambda`

, I have not figured out how.

```
(define (iterative-improve good-enough? improve)
(define (improve-procedure guess)
(if (good-enough? guess)
guess
(improve-procedure (improve guess))))
improve-procedure)
```

Using `iterative-improve`

to redefine `sqrt`

:

```
(define (average x y) (/ (+ x y) 2))
(define (square x) (* x x))
(define (sqrt x)
((iterative-improve (lambda (guess)
(< (abs (- (square guess) x))
0.001))
(lambda (guess)
(average guess (/ x guess))))
1.0))
```

…and `fixed-point`

:

```
; Fixed point
(define tolerance 0.00001)
(define (fixed-point f first-guess)
((iterative-improve (lambda (guess)
(< (abs (- guess (f guess)))
tolerance))
(lambda (guess) (f guess)))
first-guess))
```