sicp-3-5-1-3-5-2

Posted on 2015-03-02 20:24:25 +0900 in SICP Lisp

Code from the text.

(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))
(define (stream-map proc s)
  (if (stream-null? s)
      the-empty-stream
      (cons-stream (proc (stream-car s))
                   (stream-map proc (stream-cdr s)))))
(define (stream-for-each proc s)
  (if (stream-null? s)
      'done
      (begin (proc (stream-car s))
             (stream-for-each proc (stream-cdr s)))))

(define (display-stream s)
  (stream-for-each display-line s))

(define (display-line x)
  (newline)
  (display x))

(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))

(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1) high))))

(define (stream-filter pred stream)
  (cond ((stream-null? stream) the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter pred
                                     (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))

(stream-ref
   (stream-enumerate-interval 1 100)
   10)

(define (memo-proc proc)
  (let ((already-run? false) (result false))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? true)
                 result)
          result))))

3.50

(define (stream-map proc . argstreams)
  (if (null? (car argstreams))
      the-empty-stream
      (cons-stream
       (apply proc (map stream-car argstreams))
       (apply stream-map
              (cons proc (map stream-cdr argstreams))))))

(define s1 (stream-enumerate-interval 10 100))
(define s2 (stream-enumerate-interval 20 200))
(define s3 (stream-enumerate-interval 30 300))

(define test (stream-map + s1 s2 s3))
(stream-ref test 0)
(stream-ref test 1)
(stream-ref test 2)

3.51

(define (show x)
  (display-line x)
  x)

(define x (stream-map show (stream-enumerate-interval 0 10)))
0
;Value: x
(stream-ref x 5)

1
2
3
4
5

;Value: 5

(stream-ref x 7)

6
7
;Value: 7

It is confusing for me to understand this memo-proc function. All the delayed functions are cached after the first running.

3.52

(define sum 0)
(define (accum x)
  (set! sum (+ x sum))
  sum)
(define seq (stream-map accum (stream-enumerate-interval 1 20)))
; sum = 1

(define y (stream-filter even? seq))
; sum = 6

(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                         seq))
; sum = 10

(stream-ref y 7)
;Value: 136

(display-stream z)
; 10
; 15
; 45
; 55
; 105
; 120
; 190
; 210
; sum = 210

sum acts as a global value, which is a bad idea in the stream. When the delay is memorized, seq is the same no matter how many times it is called.

If the non-memorized version is used, then seq would have different result because of the sharing sum.

(define sum 0)
(define (accum x)
  (set! sum (+ x sum))
  sum)
(define seq (stream-map accum (stream-enumerate-interval 1 20)))
;seq=(1, (accum 2), (accum 3)...(accum 20))
;sum=1

(define y (stream-filter even? seq))
;y=(6, (stream-filter even? ((accum 4), (accum 5), ...)))
;sum=6

(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                         seq))
;z=(15, (stream-filter (lambda (x) (...)) ((accum 5) ...)))
;sum=15

(stream-ref y 7)
;y=(6, 24, 30, 54,...)

3.53

(1 2 4 8 16 32 …)

3.54

(define (mul-streams s1 s2)
  (stream-map * s1 s2))
(define factorials
  (cons-stream 1 (mul-streams
                  factorials
                  (integers-starting-from 2))))

3.55

(define (partial-sum s)
  (cons-stream
    (car s)
    (add-streams
      (stream-cdr s)
      (partial-sum s))))

3.56

(define S
  (cons-stream
   1 (merge (scale-stream S 2)
            (merge (scale-stream S 3)
                   (scale-stream S 5)))))

3.57

memorized version is $O(n)$ while naive version is $O(2^n)$

3.58

(define (expand num den radix)
  (cons-stream
   (quotient (* num radix) den)
   (expand (remainder (* num radix) den) den radix)))

It is long divide.

3.59

(define (integrate-series s)
  (stream-map / s integers))

(define sine-series
  (cons-stream 0 (integrate-series cosine-series)))
(define cosine-series
  (cons-stream 1
               (scale-stream
                 (integrate-series sine-series)
                 -1))

3.60

(define (mul-series s1 s2)
  (cons-stream
    (* (stream-car s1) (stream-car s2))
    (add-streams
      (scale-stream
        (stream-cdr s2)
        (stream-car s1))
      (mul-series
        (stream-cdr s1)
        s2))))

(define t
  (add-streams
    (mul-series sine-series sine-series)
    (mul-series cosine-series cosine-series)))

(display-stream t)

$(h1 + tail1) * (h2 + tail2) = h1 * h2 + h1tail2 + tail1(h2+tail2)$

3.61

(define (invert-unit-series s)
  (cons-stream 1
               (scale-stream
                 (mul-series
                   (stream-cdr s)
                   (invert-unit-series s)))))

3.62

(define (div-series num den)
   (let ((den0 (stream-car den)))
      (if (= den-const 0)
        (error "The constant term of the denominator must be nonzero")
        (scale-stream
         (mul-series
          num (invert-unit-series
                (scale-stream den (/ 1 den-const))))
         (/ 1 den-const)))))

The den should be normalized to have the $constant=1$

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------

« sicp-3-5-3 | sicp-3-4 »