sicp ch3 5 - andstudy/forge GitHub Wiki

  ;; 되풀이 방식
  (define (sum-primes a b)
    (define (iter count accum)
      (cond ((> count b) accum)
  	  ((prime? count) (iter (+ count 1) (+ count accum)))
  	  (else (iter (+ count 1) accum))))
    (iter a 0))
  
  ;; 차례열 연산 방식
  (define (sum-primes a b)
    (accumulate +
  	      0
  	      (filter prime? (enumerate-interval a b))))

  (car (cdr (filter prime?
  		  (enumerate-interval 10000 1000000))))

  (car (cons 1 2))
  (cdr (cons 1 2))
  (stream-car (cons-stream 'x 'y))
  (stream-cdr (cons-stream 'x 'y))
  
  (cons-stream <a> <b>) ==> (cons <a> (delay <b>))
  
  (delay <exp>) ==> (lambda () <exp>)
  
  (define (force delayed-object)
    (delayed-object))

  (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)))))

  (stream-car
   (stream-cdr
    (stream-filter prime?
  		 (stream-enumerate-interval 10000 1000000))))
  ; 자세한 동작은 책 418p, 420p 참고
  
  (car (cdr (filter prime?
  		  (enumerate-interval 10000 40000))))

  ; 정수
  (define (integers-starting-from n)
    (cons-stream n (integers-starting-from (+ n 1))))
  (define integers (integers-starting-from 1))
  ; 7로 나누어떨어지지 않는 정수
  (define (divisible? x y) (= (remainder x y) 0))
  (define no-sevens
    (stream-filter (lambda (x) (not (divisible? x 7)))
  		 integers))
  ; 피보나치 수열
  (define (fibgen a b)
    (cons-stream a (fibgen b (+ a b))))
  (define fibs (fibgen 0 1))

  ; 소수 스트림
  (define (sieve stream)
    (cons-stream
     (stream-car stream)
     (sieve (stream-filter
  	   (lambda (x)
  	     (not (divisible? x (stream-car stream))))
  	   (stream-cdr stream)))))
  (define primes (sieve (integers-starting-from 2)))

  ; 재귀 정의 소수 스트림
  (define primes
    (cons-stream
     2
     (stream-filter prime? (integers-starting-from 3))))
  
  (define (prime? n)
    (define (iter ps)
      (cond ((> (square (stream-car ps)) n) true)
  	  ((divisible? n (stream-car ps)) false)
  	  (else (iter (stream-cdr ps)))))
    (iter primes))
   }}}
   - 어떤 계산 시점에서 다음에 소수인지 따져 보는 데 필요한 만큼 primes 스트림이 만들어져있음.
  
   * ex3-55
   {{{#!gcode
  ;; ex3-55.scm
  (define (partial-sums ps)
    (cons-stream (stream-car ps)
  	       (add-streams (stream-cdr ps)
  			   (partial-sums ps))))

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

  ;; pi/4 = 1 - 1/3 + 1/5 - 1/7 ....
  (define (pi-summands n)
    (cons-stream (/ 1.0 n)
  	       (stream-map - (pi-summands (+ n 2)))))
  
  (define pi-stream
    (scale-stream (partial-sums (pi-summands 1)) 4))

  (define (euler-transform s)
    (let ((s0 (stream-ref s 0))
  	(s1 (stream-ref s 1))
  	(s2 (stream-ref s 2)))
      (cons-stream (- s2 (/ (square (- s2 s1))
  			  (+ s0 (* -2 s1) s2)))
  		 (euler-transform (stream-cdr s)))))
  ;(display-stream (euler-transform pi-stream))

  (define (make-tableau transform s)
    (cons-stream s
  	       (make-tableau transform
  			     (transform s))))
  
  (define (accelerated-sequence transform s)
    (stream-map stream-car
  	      (make-tableau transform s)))
  
  (display-stream (accelerated-sequence euler-transform pi-stream))

  ;;;;;;;; 간단히 이렇게...
  (define prime-pairs
    (stream-filter (lambda (pair)
  		   (prime? (+ (car pair) (cadr pair))))
  		 int-pairs))
  
  ;;;;;;;; 문제는 int-pairs (442p)
  (define (interleave s1 s2)
    (if (stream-null? s1)
        s2
        (cons-stream (stream-car s1)
  		   (interleave s2 (stream-cdr s1)))))
  
  (define (pairs s t)
    (cons-stream
     (list (stream-car s) (stream-car t)) ;;;;;;;;; (S0 T0)
     (interleave ;;;;;;;; stream-append 같은 접근법은 불가능 (443p)
      (stream-map (lambda (x) (list (stream-car s) x))
  		(stream-cdr t)) ;;;;;;;;;; (S0 T1) (S0 T2) (S0 T3) ...
      (pairs (stream-cdr s) (stream-cdr t))))) ;;;;;;;;;;;; 재귀
  
  (define int-pairs (pairs integers integers))

  (define (integral integrand initial-value dt)
    (define int
      (cons-stream initial-value
  		 (add-streams (scale-stream integrand dt)
  			      int)))
    int)

  (define random-numbers
    (cons-stream random-init
  	       (stream-map rand-update random-numbers)))
  
  (define (map-successive-pairs f s)
    (cons-stream
     (f (stream-car s) (stream-car (stream-cdr s)))
     (map-successive-pairs f (stream-cdr (stream-cdr s)))))
  
  (define cesaro-stream
    (map-successive-pairs (lambda (r1 r2) (= (gcd r1 r2) 1))
  			random-numbers))
  
  (define (monte-carlo experiment-stream passed failed)
    (define (next passed failed)
      (cons-stream
       (/ passed (+ passed failed))
       (monte-carlo
        (stream-cdr experiment-stream) passed failed)))
    (if (stream-car experiment-stream)
        (next (+ passed 1) failed)
        (next passed (+ failed 1))))
  
  (define pi
    (stream-map (lambda (p) (sqrt (/ 6 p)))
  	      (monte-carlo cesaro-stream 0 0)))
  
  (stream-ref pi 100)