;;;            With Assignment

(define (estimate-pi n)
  (sqrt (/ 6 (monte-carlo cesaro n))))

(define (cesaro)
  (= (gcd (rand) (rand)) 1))

(define (monte-carlo experiment trials)
  (define (iter remaining passed)
    (cond ((= remaining 0)
           (/ passed trials))
          ((experiment) 
           (iter (- remaining 1)
                 (+ passed 1)))
          (else 
           (iter (- remaining 1)
                 passed))))
  (iter trials 0))

(define rand
  (let ((x random-seed))
    (lambda ()
      (set! x (rand-update x))
      x)))

;;;          Without Assignment

(define (estimate-pi n)
  (sqrt (/ 6 (monte-carlo-cesaro n))))

(define (monte-carlo-cesaro trials)
  (define (iter remaining passed x0)
    (let ((x1 (rand-update x0)))
      (let ((x2 (rand-update x1)))
        (cond ((= remaining 0)
               (/ passed trials))
              ((= (gcd x1 x2) 1)
               (iter (- remaining 1)
                     (+ passed 1)
                     x2))
              (else 
               (iter (- remaining 1)
                     passed
                     x2))))))
  (iter trials 0 random-seed))

;;; Monolithic Program

(define (sum-odd-squares tree)
  (cond ((null? tree) 0)
        ((not (pair? tree))
         (if (odd? tree) (square tree) 0))
        (else 
         (+ (sum-odd-squares (car tree))
            (sum-odd-squares (cdr tree))))))


;;; Sequence-based program

(define (sum-odd-squares tree)
  (fold-right + 0
     (map square
        (filter odd?
           (enumerate-tree tree)))))


(define (enumerate-tree tree)
  (cond ((null? tree) '())
        ((not (pair? tree)) (list tree))
        (else
         (append 
           (enumerate-tree (car tree))
           (enumerate-tree (cdr tree))))))

;;; Monolithic Program

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



;;; Sequence-based program

(define (sum-primes a b)
  (fold-right + 0
     (filter prime?
        (enumerate-interval a b))))



;; But: (sum-primes 10000 10000000)

;;; But it is better, because the delayed 
;;; procedure is memoized.

(define (memo-thunk thunk)
  (let ((already-run? #f) (result #f))
    (lambda ()
      (cond (already-run? result)
            (else
              (set! result (thunk))
              (set! already-run? #t)
              result)))))

;;; 
;;; (delay <e>) 
;;;    ==> (memo-thunk (lambda () <e>))

;;; We need a stream library

(define (stream-ref s n)
  (if (= n 0) 
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(define (stream-map proc s)
  (if (empty-stream? s)
      the-empty-stream
      (cons-stream (proc (stream-car s))
         (stream-map proc (stream-cdr s)))))

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

(define (stream-for-each proc s)
  (cond ((stream-null? s) 'done)
        (else (proc (stream-car s))
              (stream-for-each proc 
                  (stream-cdr s)))))

;;; ... etc. ...

;;;           Infinite Streams

(define (integers-from n)
  (cons-stream n (integers-from (+ n 1))))

(define natural-numbers
  (integers-from 1))


(define (divisible? x y)
  (= (remainder x y) 0))

(define no-sevens
  (stream-filter (lambda (x) 
                   (not (divisible? x 7)))
                 natural-numbers)))

;;; (stream-ref no-sevens 100) ==> 117


(define (fibgen a b)
  (cons-stream a (fibgen b (+ a b))))

(define fibs (fibgen 0 1))

;;; (stream-ref fibs 20) ==> 6765

;;;	     Implicit Definition


(define natural-numbers
  (cons-stream 1
	       (stream-map (lambda (x) (+ x 1))
			   natural-numbers)))

;;; (stream-ref natural-numbers 10) ==> 11



;;;         Sieve of Eratosthenes

(define (sieve s)
  (let ((h (stream-car s)))
    (cons-stream h
      (sieve (stream-filter
                (lambda (x) 
                  (not (divisible? x h)))
                (stream-cdr s))))))

(define primes (sieve (integers-from 2)))

;;; (stream-ref primes 50)  ==>  233

;;; (stream-ref primes 500) ==> 3581

;;;	   SICVT ERAT IN PRINCIPIO

;;; Assuming only infinite streams.......

;;; If we define map-pairs as

(define (map-pairs f s)
  (cons-stream 
     (f (stream-car s) 
        (stream-car (stream-cdr s)))
     (map-pairs f (stream-cdr s))))

;;; then we get a beautiful way to write
;;; the cesaro experiment without assignment!

(define random-numbers
  (cons-stream random-seed
    (stream-map rand-update random-numbers)))

(define cesaro-stream
  (map-pairs 
     (lambda (r1 r2) (= (gcd r1 r2) 1))
     random-numbers))

(define (monte-carlo e-stream pass fail)
  (define (next pass fail)
    (cons-stream (/ pass (+ pass fail))
       (monte-carlo (stream-cdr e-stream)
                    pass fail)))
  (if (stream-car e-stream)
      (next (+ pass 1) fail)
      (next pass (+ fail 1))))

(define pi-stream
  (stream-map
     (lambda (p)
        (if (= p 0) 
            'infinity
            (sqrt (/ 6 p))))
     (monte-carlo cesaro-stream 0 0)))

(stream-ref pi-stream 1000)
;Value: 3.1455624976605745

;;; Signals

(define (add-streams s1 s2)
  (cons-stream (+ (stream-car s1)
                  (stream-car s2))
    (add-streams (stream-cdr s1) 
                 (stream-cdr s2))))

(define (scale-stream s x)
  (stream-map (lambda (y) (* x y)) s))

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