0
\$\begingroup\$

Exercise 1.31

a. The sum procedure is only the simplest of a vast number of similar abstractions that can be captured as higher-order procedures.51 Write an analogous procedure called product that returns the product of the values of a function at points over a given range. Show how to define factorial in terms of product. Also use product to compute approximations to using the pi / 4 = (2/3) * (4/3) * (4/5) * (6/5) * (6/7) * (8/7) ...

b. If your product procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

I wrote the following:

Recursive:

(define (product term a next b)
  (cond 
    ((> a b) 1)
    (else (* (term a) (product term (next a) next b)))))

Iterative:

(define (i-product term a next b)
  (cond ((> a b) null)
      (else 
       (define (iter a result)
         (cond ((> a b) result)
               (else (iter (next a) (* (term a) result)))))
       (iter a 1))))

Multiply-integers [test - does (product ...) work?]

(define (identity x) x)
(define (inc x) (+ 1 x))
(define (multiply-integers a b) (i-product identity a inc b))

Compute pi:

(define (square x) (* x x))
(define (compute-pi steps)
  (define (next n) (+ n 2.0))
  (* 8.0 (* steps 2) (/ (i-product square 4.0 next (* (- steps 1) 2)) 
              (i-product square 3.0 next (* steps 2)))))

Factorial:

(define (factorial n)
  (define (next n) (+ n 1))
  (i-product identity 1 next n))

What do you think of my solution?

\$\endgroup\$

migrated from stackoverflow.com Mar 30 '11 at 3:11

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ I meant to post this at codereview.stackexchange.com - can it be migrated? \$\endgroup\$ – jaresty Mar 30 '11 at 2:52
  • \$\begingroup\$ @Joshua: Yes. Click "flag", "it needs ♦ moderator attention", then "other", and fill in the textbox requesting this. :-) (I've also requested a migration for you in the mod chat room, in case they monitor that more frequently. ;-)) \$\endgroup\$ – Chris Jester-Young Mar 30 '11 at 3:07
  • \$\begingroup\$ It turned out that the mod chat room was indeed monitored more frequently (thanks Shog9!), but, in future, you can flag your post yourself anyway. SO mods are meant to be pretty active, and should see your flag pretty much straight away. :-) \$\endgroup\$ – Chris Jester-Young Mar 30 '11 at 3:47
1
\$\begingroup\$

Since your definitions have only two cond clauses, you may replace cond with if. Your iterative definition is a departure from the example of sum. It should return 1 (product identity) when a is greater than b, not null. This makes the outer cond unnecessary.

Your definition of compute-pi suffers from imprecision of float operations (it fails to produce meaningful values for n > 85). It would be better to convert to float after computing the approximating fraction.

(define (product term a next b)
  (if (> a b)
      1
      (* (term a) (product term (next a) next b))))

(define (i-product term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* (term a) result))))
  (iter a 1))

(define (compute-pi steps)
  (define (next n) (+ n 2))
  (* 8.0 (* steps 2) (/ (i-product square 4 next (* (- steps 1) 2)) 
                        (i-product square 3 next (* steps 2)))))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.