| |
Exercises 1.30 - 1.33
| | (ns e1-30-to-33
(:use [util.util :only (id compose square curry)])
(:use [clojure.contrib.math :only (gcd sqrt)])
(:use [clojure.contrib.test-is :only (deftest is run-tests)]))
1.30
The sum procedure in the previous chapter generates a linear recursion.
The procedure can be rewritten so that the sum is performed iteratively.
| |
|
| | (defn sum-iter [term a nextf b]
(defn iter [a result]
(if (> a b)
result
(iter (nextf a) (+ result (term a)))))
(iter a 0))
|
| | (defn sum-ints [a b]
(sum-iter id a inc b))
|
| | (deftest test-sum-ints
(is (= (sum-ints 1 10) 55)))
1.31
The sum procedure is only the simplest of a vast number of similar
abstractions that can be captured as higher-order procedures. Write an
analogous procedure called product that returns the product of the values
of a function at points over a given range.
| |
|
| | (defn product-31 [term a next b]
(if (> a b)
1
(* (term a)
(product-31 term (next a) next b))))
|
| | (deftest product-test-31
(is (= (product-31 id 1 inc 10) 3628800)))
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.
| |
|
| | (defn product-iter [term a nextf b]
(let [iter (fn [a result]
(if (> a b)
result
(recur (nextf a) (* result (term a)))))]
(iter a 1)))
|
| | (deftest product-iter-test
(is (= (product-iter id 1 inc 10) 3628800)))
Show how to define factorial in terms of product:
| |
|
| | (defn fact [x]
(product-31 id 1 inc x))
|
| | (defn twoinc [x]
((compose inc inc) x))
Also use product to compute approximations to \(pi\):
| |
Calculates pi with the specified accuracy
| | (defn pi
[acc]
(let [upper (product-31 id 4 twoinc (- acc 1)) ; 4*6*8*...*k, k < acc
lower (product-31 id 3 twoinc acc) ; 3*5*7*...*l, l <= acc
factor (if (even? acc)
(dec acc)
(acc))]
(* 4 (/
(* 2 (square upper)) ; 4*4*6*6*8*8*...*k*k, k < acc
(* factor (square (/ lower factor))))))) ; 3*3*5*5*...*(l-2)*(l-2)*l, l <= acc
|
| | (deftest pi-test
(is (= (double (pi 600)) 3.138971384492951)))
1.32
Show that sum and product (exercise 1.31) are both special cases of a still
more general notion called accumulate that combines a collection of terms,
using some general accumulation function:
(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.
| |
|
| | (defn accumulate [combiner zero term a nextf b]
(if (> a b)
zero
(combiner (term a)
(accumulate combiner zero term (nextf a) nextf b))))
If your accumulate 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.
| |
|
| | (defn accumulate-iter [combiner zero term a nextf b]
(let [iter (fn [a result]
(if (> a b)
result
(recur (nextf a) (combiner result (term a)))))]
(iter a zero)))
|
| | (defn sum [term a nextf b]
(accumulate + 0 term a nextf b))
|
| | (defn product [term a nextf b]
(accumulate * 1 term a nextf b))
|
| | (deftest sum-test
(is (= (sum square 1 inc 10) 385)))
|
| | (deftest product-test
(is (= (product square 1 inc 10) 13168189440000)))
1.33
You can obtain an even more general version of accumulate (exercise 1.32) by
introducing the notion of a filter on the terms to be combined. That is,
combine only those terms derived from values in the range that satisfy a
specified condition. The resulting filtered-accumulate abstraction takes the
same arguments as accumulate, together with an additional predicate of one
argument that specifies the filter. Write filtered-accumulate as a
procedure.
| |
|
| | (defn filtered-acc [filterf combiner zero term a nextf b]
(if (> a b)
zero
(if (filterf a)
(combiner (term a)
(filtered-acc filterf combiner zero term (nextf a) nextf b))
(filtered-acc filterf combiner zero term (nextf a) nextf b))))
|
| | (defn prime-for? [n x]
(= (gcd n x) 1))
|
| | (deftest prime-test
(is (= (prime-for? 10 4) false)))
|
| | (defn prime? [x]
(let [iter (fn [nextf]
(if (> nextf (sqrt x)) ; up to the square of x
true
(if (> (rem x nextf) 0)
(recur (inc nextf))
false)))]
(if (= x 2) false (iter 2))))
|
| | (deftest prime-test-2
(is (= (prime? 3) true))
(is (= (prime? 37) true))
(is (= (prime? 254) false)))
Show how to express the following using filtered-accumulate:
| |
- the sum of the squares of the prime numbers in the interval \(a\) to \(b\):
| | (defn squares [a b]
(filtered-acc prime? + 0 square a inc b))
|
| | (deftest squares-test
(is (= (squares 1 10) 84)))
- the product of all the positive integers less than \(n\) that are relatively
prime to \(n\) (i.e., all positive integers \(i < n\) such that \(GCD(i,n) = 1\)).
| | (defn prod-less-than [n]
(filtered-acc (curry prime-for? n) + 0 id 1 inc n))
|
| | (deftest squares-test
(is (= (prod-less-than 10) 20)))
| | |