# SICP Chapter 1.3

Generalizing functions with hardwired values

# Chapter 1.3: Formulating Abstractions With Higher-Order Procedures

## 1.3.1

1.3 presents the following higher-order function:

``````(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))``````

It’s worth noting that `sum` is not as general as it could be. It hardwires in a terminal value of 0, and the `+` and `>` operator & conditional. Its type would be something like `sum :: (Num a) => (a -> a) -> a -> (a -> a) -> a -> a`; a more general approach would be to require a general boolean function rather than a particular value.

iterate is similar, but note that it has a type signature that initially seems simpler and less powerful: `iterate :: (a -> a) -> a -> [a]`. Surely the more parameterizable a function, the more general it is? `iterate` has but 1 function argument, while `sum` has 2.

But `iterate` has 2 arguments in a sense, when we remember how it generates an infinite list—we can think of it as the zeroth entry is `x`, the first entry `f x`, the 2nd entry is `f (f x)`, the 3rd entry is `f (f (f x))`, and so on1. The missing function is whatever is calling `iterate` and using its values; in `sum`, the termination is explicitly handled by a function because the evaluation scheme in Scheme is strict.

Here’s an example. If we called `iterate (^3) 2`, we would get the infinite list `[2,8,512,134217728,2417851639229258349412352..]`; but `sum` clearly has a stopping case. So we compose `iterate` with takeWhile: `iterate` gets the seed value and the knowledge of how to keep changing the seed value, and `takeWhile` gets the knowledge of when the seed value has changed enough.

This will be useful for approximation. But note that it’s not useful for straight summing like `sum-cubes`, because `iterate` uses the passed-in function to generate the next target from the old target, while `sum` has the passed-in function doing something else entirely (moving from old to new is hardwired to use the function `(+1)`). So if we wrote the obvious Haskell `summation` and `sumCube` definitions, they would be utterly wrong: `sumCube 1 10` will loop because 13 = 1, and if we tried `sumCube 2 10`, it’d still be wrong—we’d get `[2,8]` because the test will return false for 83 < 10.

``````summation cond next seed = takeWhile cond (iterate next seed)
sumCube start end = summation (< end) (^3) start``````

To rewrite `sum`, we need to pay attention to what dependencies are where. Given the parameters `a b`, we can get the targets with just `[a..b]`; then, we take whatever function and `map` it onto the targets: `foo f a b = map f [a..b]`; then we fold the resulting list into a final answer: `foo f a b = sum (map f [a..b])`, and finally:

``sumCube start end = foo (^3) start end``

But `sum` has 4 parameters, not 3. The `[a..b]` hides the `(+1)` or `inc` specification.

### Exercise 1.29

Pseudo-code from the specification:

``````simpson f a b n =
(h/x) * [y 0 + 4 * y 1 + 2 * y 2 ... + y n]
where h = (b - a) / n
y k = f (a + k * h)``````

The tricky part is the middle of the summation. We need to multiply by 2 or 4 except for the first and last terms. Kind of hard to express that as a simple recursion. We could generate that middle directly by generating the indices (`[1..(n-1)]`), running `y` on them (`map y`), creating an infinite list of coefficients (`cycle [2,4]`), and combining the coefficients with the transformed indices (`zipWith (*)`), and then directly specify the `y 0` and `y n` calls so we have something like:

``````simpson :: (Fractional a, Enum a) => (a -> a) -> a -> a -> a -> a
simpson f a b n =
(h/3) * y 0 * sum (zipWith (*) (cycle [2,4]) (map y [1..(n-1)])) * y n
where h = (b - a) / n
y k = f (a + k * h)``````

Ugly, though it works, for example

``simpson cube 0 1 1000 → 0.2496671666666665``

(This has diminishing returns; a n of 1000000 gives the three-places more precise 0.24999966666716916 but is much slower.)

If we didn’t want to use the various Prelude operators in a Scheme version, we’d have to drag around state in the form of a variable.

``````(define (simpson f a b n)
(let ((h (/ (- b a) n)))
(define (simpson-term k)
(*  (f (+ a (* k h)))
(cond ((or (= k 0) (= k n)) 1)
((odd? k) 4)
(else 2))))
(*  (/ h 3)
(sum simpson-term 0 inc n))))``````

Interestingly, Dr. Scheme evaluates `(simpson-integral cube 0 1 1000)` to 1⁄4. I don’t know how it can be so precise.

### Exercise 1.30

``````(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))``````
``````(define (sum term a next b)
(define (iter a result)
(if <??>
<??>
(iter <??> <??>)))
(iter <??> <??>))``````

Ought to be straightforward by this point (especially since half the battle is figuring out the auxiliary function `iter a result`):

``````(define (sum term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ result (term a)))))
(iter a 0))``````

### Exercise 1.31

Our `sum` rewritten for multiplication is of course (modulo better variable names):

``````(define (product f begin increase end)
(if (> begin end)
1
(* (f begin)
(product f (increase begin) increase end))))``````

All we had to change was the ‘seed’ and the inner function (`*` versus `+`).

Writing a `factorial` requires a little imagination, but here Haskell prevents me from having to think too much; Haskell’s product has the type signature `Num a => [a] -> a`, so immediately the obvious way to define `factorial` is to generate a list of the right length:

``factorial n = product [1..n]``

How can we generate such a list with this Scheme function? We have to pass in 2 functions and 2 integers which will somehow do this.

The answer is to make our first function do nothing, and the second function just increment the seed; an example:

``````(product (lambda (a) a) 1 (lambda (g) (+ g 1)) 5)
→
120``````

The `(lambda (a) a)` is bound to the variable `f`, which gets called on the first multiplication, but does nothing—exactly as needed. Then `(lambda (g) (+ g 1))` takes care of generating the next entry in the Scheme equivalent of `[1..n]`.

#### Monoids

A worldly Haskeller will look at this and immediately think, ‘an initial seed value, and some way of combining values… could this idea be a monoid‽’

As sigfpe’s excellent tutorial or Learn You A Haskell or Real World Haskell will tell us, yes—this is a monoid. In fact, integers (our topic) form two different monoids, one for addition (Sum) and one for multiplication (Product).

The `Monoid` typeclass requires the following:

``````class Monoid a where
mempty  :: a
mappend :: a -> a -> a
mconcat :: [a] -> a``````

`mempty` is our ‘seed’ value—it is the identity. For Sum, 0 + n = n; for Product, 1 × n = n.

`mappend` is how to combine 2 such monoids. Both `(+)` and `(*)` have the right type signature: `Num a => a -> a -> a`.

`mconcat` can be automatically defined from `mempty` and `mappend`—you just prefix a `mempty` onto the list, and then proceed to `mappend` your way down it.

This works out perfectly for `+` and `*`:

``````mconcat [1..5] -- for Product
→
fold [mempty, 1, 2, 3, 4, 5] -- not the actual fold; artistic license
→
mempty `mappend` 1 `mappend` 2 `mappend` 3 `mappend` 4 `mappend 5
→
1 `mappend` 1 `mappend` 2 `mappend` 3 `mappend` 4 `mappend 5
→
1 * 1 * 2 * 3 * 4 * 5
→
120

mconcat [1..5] -- for Sum
→
fold [mempty, 1, 2, 3, 4, 5] -- not the actual fold; artistic license
→
mempty `mappend` 1 `mappend` 2 `mappend` 3 `mappend` 4 `mappend 5
→
0 `mappend` 1 `mappend` 2 `mappend` 3 `mappend` 4 `mappend` 5
→
0 + 1 + 2 + 3 + 4 + 5
→
15``````

Notice that right up to the final steps everything was the same.

If we wanted to use the Sum or Product monoids in actual code, we would use the Data.Monoid library, which gives us Sum and Product on everything in the Num typeclass:

``````import Data.Monoid
...
mconcat (map Product [1..5])
→
Product {getProduct = 120}

mconcat (map Sum [1..5])
→
Sum {getSum = 15}``````

So, `mconcat` is basically our `sum` or `product` but abstracted away from a specific monoid and how to generate the `[a]` argument.

A great many data structures or datatypes are monoids; they’re worth knowing about.

### Exercise 1.32

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

`accumulate` takes as arguments the same term and range specifications as `sum` and `product`, together with a combiner procedure (of two arguments) that specifies how the current term is to be combined with the accumulation of the preceding terms and a null-value that specifies what base value to use when the terms run out. Write `accumulate` and show how `sum` and `product` can both be defined as simple calls to `accumulate`.”

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

Then we define `sum` and `product` by specializing `accumulate` in its first 2 arguments:

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

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

#### With Monoids

So. `combiner` takes 2 arguments of the same data type (such as `Int` and `Int`) and produces a third argument of the same data type; that is, `combiner :: a -> a -> a`, or since we just covered monoids, we’ll say (Monoid a) => a -> a -> a. The first hit is `Data.Monoid mappend :: Monoid a => a -> a -> a`.

The null-value is simply that same data type, (Monoid a) => a; the first hit is `Data.Monoid mempty :: Monoid a => a`

With an instance of the Monoid typeclass, we can scrap the null-value and `combiner` arguments since they are pre-defined. We just need the range (`a` and `b`) and how to increment (`next`) since the Monoid typeclass doesn’t cover that. A fairly literal translation of the previous section:

``````accumulate :: (Ord a, Monoid a1) => (a -> a1) -> a -> (a -> a) -> a -> a1
accumulate term a next b =
let iter a' result = if a' > b
then result
else iter (next a') (term a' `mappend` result)
in
iter a mempty

product :: (Ord a1, Num a) => (Product a1 -> Product a) -> a1 -> (Product a1 -> Product a1) -> a1 -> a
product a b c d = getProduct (accumulate a (Product b) c (Product d))

sum :: (Ord a1, Num a) => (Sum a1 -> Sum a) -> a1 -> (Sum a1 -> Sum a1) -> a1 -> a
sum a b c d = getSum (accumulate a (Sum b) c (Sum d))``````

Usage would look like

``sum id 1 (\(Sum a) -> (Sum (a+1))) 5``

(This example evaluates to 15, and is equivalent to `sum [1..5]`.)

### Exercise 1.33

I cheat a little here, and just rewrite `combiner` to get the filter effect:

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

Again we specialize (assuming the obvious definitions for `square`, `inc`, `prime?`, and `gcd`):

``````(define (sum-squared-primes a b)
(accumulate-filter + 0 square a inc b prime?))

(define (product-relative-prime n)
(define (relative? k) (= (gcd k n) 1))
(filtered-accumulator * 1 (lambda x x) 1 inc (- 1 n) relative?))``````

## 1.3.2

The remarks on scoping and how lambda is what lurks behind the sugar of `let` are true in Haskell as far as I know, and thus a bit boring to me.

### Exercise 1.34

We’re asked to evaluate `(f f)` given:

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

Quickly eyeballing it, I assumed it would turn out to be an infinite loop, as it became something like `(f (f (f (f (f...)))))`. But when I calculate it out by hand, I realize that is not the case!

1. `(f f)`

2. `(lambda (x) (x 2) f)`

3. `(f 2)`

4. `(lambda (x) (x 2) 2)`

5. `(2 2)`

6. Dr. Scheme error: “procedure application: expected procedure, given: ‘2’; arguments were: ‘2’”

## 1.3.3

1. This is the idea; the actual implementation is more syntactically efficient: `iterate f x = x : iterate f (f x)`.↩︎