High-Order Procedure(Iterative)

eg.1 sum of integer

$$ \sum\nolimits_{i=a} ^{b}{i} $$

1
2
3
4
5
6
7
; primitive procedure 1+ 1-
(define (soi a b)
    (if (> a b)
    0
    (+ (soi (1+ a) b) a)
    )
)

eg.2 sum of square

$$ \sum\nolimits_{i=a}^{b}{i^2} $$

1
2
3
4
5
6
7

(define (soq a b)
    (define (square x)(* x x))
    (if (> a b)
    0
    (+ (soi (1+ a) b) (square a)))
)

eg.3 Leibnitz’s formula

Following formula is designed to find value of

$$ \frac{\pi}{8} = \lim_{b\to+\infty}\sum\nolimits_{i=a;by4}^{b}\frac{1}{{i(i+1)}} $$

1
2
3
4
5
6
7
(define (pi-sum a b)
    (if (> a b)
    0
    (+ (pi-sum (+ 4 a) b)
        (/ 1 (* a (+1 a)))
    ))
)

general pattern of above example

1
2
3
4
5
6
7
(define (<name> a b)
    (if (> a b)
    0
    (+ (<name> (<next> a) b) 
        (<handle> a))
    )
)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
(define (sum a identity next b)
    (if (> a b)
    0
    (+ (sum (next a) b) 
        (identity a))
    )
)

(define (soi a b)
    (define (identity x) x)
    (sum identity a 1+ b)
)

(define (soq a b)
    (define (identity x) (* x x))
    (sum identity a 1+ b)
)

Iterative

1
2
3
4
5
6
7
8
(define (sum term a next)
    (define (iter j ans)
        (if (> j b)
            ans
            (iter (next j)
                (+ (term j)   
                    ans))))
    (iter a 0))

eg.4 Heron of Alexandria’s method

It is used to compute square roots.

It can be viewed as a iterative procedure finding a fixed point.

Abstraction of this method:

1
2
3
4
5
(define (sqrt x )
    (fixed-point 
        (lambda (y)
            (average (/ x y) y)) 1)
)

Details of it:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
; f: method to get close to fixed-point

(define (fixed-point f start)
    (define (iter old new)
        (if (close_enough? old new)
            new
            (iter new (f new)))
    )
    (iter start (f start))
)

eg.5 Average Damp

1
2
3
4
5
6
7
(define (sqrt x)
    (fixed-point 
        (average_damp 
            (lambda (y))
            (/ x y))
    1)
)

1
2
3
4
5
6
7
(define average_damp
    (lambda (f)
        (lambda (x) 
            (average (f x) x)
        )
    )
)

the same as below

1
2
3
4
(define (average-damp f)
    (define (foo x)
        (average (f x) x))
    foo)

eg.6 Newton’s method

To find a y to such that $$ f(y) = 0 $$ start with a guess y0

$$ y_{n+1} = y_{n} - {\frac{f(y_{n})}{\frac{\mathrm{d} f}{\mathrm{d} y}|_{y=y_n}}} $$

Apply this method to compute a sqrt root of x:

1
2
3
4
5
6
(define (sqrt x)
    (newton (lambda (y) 
            (- x (square y))
             )
    1)
)

Details:

1
2
3
4
5
6
7
(define (newton f guess)
    (define df (deriv f))
    (fixed-point
        (lambda (x) (- x (/ (f x) (df x)))) 
        guess
    )
)

How to define deriv?

$$ f’(x) = \frac{f(x+{\mathrm{d x}})-f(x)}{\mathrm{d} x} $$

1
2
3
4
5
6
7
(define deriv
    (lambda (f)
        (lambda (x)
            (/ (- (f (+ x dx))
                  (f x))
                dx)))
)

$$ {\mathrm{d} x}? $$

1
2
; an ugly but simple method
(define dx 0.0000001)