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].

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

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

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

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

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))

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))

sum id 1 (\(Sum a) -> (Sum (a+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?))

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’”