Exercises in this lecture   Go to the notes, in which this exercise belongs -- Keyboard shortcut: 'u'   Alphabetic index   Course home   

Exercise solution:
A stream that converges to the square root a number


Here is a possible solution:

(define (improve-sqrt-guess guess x)
 (/ (+ guess (/ x guess)) 2))

(define (sqrt-stream x)
  (cons-stream
    1.0
    (map-stream (lambda (g) (improve-sqrt-guess g x))
                (sqrt-stream x))))

; An alternative definition of sqrt-stream, using the higher-order functions flip and curry2
(define (sqrt-stream-alternative x)
  (cons-stream 1 (map-stream ((curry2 (flip improve-sqrt-guess)) x) (sqrt-stream-alternative x))))

(define (curry2 f)
    (lambda(x)
      (lambda(y)
        (f x y))))

(define (flip f)
    (lambda (x y)
      (f y x)))

; Below we reproduce some of the basic stream functions, on which sqrt-stream depends.

(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream x y)
     (cons x (delay y)))))

(define head car)

(define (tail stream) (force (cdr stream)))

(define empty-stream? null?)

(define the-empty-stream '())


(define (stream-section n stream)
  (cond ((= n 0) '())
        (else (cons (head stream)
              (stream-section 
                (- n 1)
               (tail stream))))))


(define (map-stream f stream)
  (cond ((empty-stream? stream) the-empty-stream)
        (else (cons-stream (f (head stream)) (map-stream f (tail stream))))))