---
title: SICP Chapter 1.3
description: Generalizing functions with hardwired values
tags: Haskell, Scheme, computer-science, tutorial
created: 09 Jan 2010
modified: 13 Aug 2011
status: in progress
confidence: log
importance: 3
cssExtension: drop-caps-yinit
...
# Chapter 1.3: Formulating Abstractions with Higher-Order Procedures
## 1.3.1
[1.3](http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3) presents the following higher-order function:
~~~{.Scheme}
(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](!Hoogle) 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 2^nd^ entry is `f (f x)`, the 3^rd^ entry is `f (f (f x))`, and so on^[This is the idea; the actual implementation is more syntactically efficient: `iterate f x = x : iterate f (f x)`.]. 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](!Wikipedia "Function composition") `iterate` with [takeWhile](!Hoogle): `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 $1^3=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 $8^3<10$.
~~~{.Haskell}
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:
~~~{.Haskell}
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:
~~~{.Haskell}
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:
~~~{.Haskell}
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
~~~{.Haskell}
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.
~~~{.Scheme}
(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 $\frac{1}{4}$. I don't know how it can be so precise.
### Exercise 1.30
~~~{.Scheme}
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))
~~~
~~~{.Scheme}
(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`):
~~~{.Scheme}
(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):
~~~{.Scheme}
(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](!Hoogle) 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:
~~~{.Haskell}
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:
~~~{.Scheme}
(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](!Wikipedia)*‽'
As [sigfpe's](http://blog.sigfpe.com/2009/01/haskell-monoids-and-their-uses.html) excellent tutorial or [_Learn You A Haskell_](http://learnyouahaskell.com/functors-applicative-functors-and-monoids#monoids) or [_Real World Haskell_](http://book.realworldhaskell.org/read/data-structures.html#id637702) will tell us, yes---this is a monoid. In fact, integers (our topic) form two different monoids, one for addition ([Sum](!Hoogle)) and one for multiplication ([Product](!Hoogle)).
The `Monoid` typeclass requires the following:
~~~{.Haskell}
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 `*`:
~~~{.Haskell}
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](!Hoogle) library, which gives us Sum and Product on everything in the [Num](!Hoogle) typeclass:
~~~{.Haskell}
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`."
~~~{.Scheme}
(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:
~~~{.Scheme}
(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](!Hoogle). The first hit is `Data.Monoid mappend :: Monoid a => a -> a -> a`.
The null-value is simply that same data type, [(Monoid a) => a](!Hoogle); 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:
~~~{.Haskell}
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
~~~{.Haskell}
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:
~~~{.Scheme}
(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`):
~~~{.Scheme}
(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:
~~~{.Scheme}
(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