sicp exercise 3.56

;; Exercise 3.56.  A famous problem, first raised by R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, let us call the required stream of numbers S and notice the following facts about it.

;; * S begins with 1.
;; * The elements of (scale-stream S 2) are also elements of S.
;; * The same is true for (scale-stream S 3) and (scale-stream 5 S).
;; * These are all the elements of S.

;; Now all we have to do is combine elements from these sources. For this we define a procedure merge that combines two ordered streams into one ordered result stream, eliminating repetitions:

;; (define (merge s1 s2)
;;   (cond ((stream-null? s1) s2)
;;         ((stream-null? s2) s1)
;;         (else
;;          (let ((s1car (stream-car s1))
;;                (s2car (stream-car s2)))
;;            (cond ((< s1car s2car)
;;                   (cons-stream s1car (merge (stream-cdr s1) s2)))
;;                  ((> s1car s2car)
;;                   (cons-stream s2car (merge s1 (stream-cdr s2))))
;;                  (else
;;                   (cons-stream s1car
;;                                (merge (stream-cdr s1)
;;                                       (stream-cdr s2)))))))))

;; Then the required stream may be constructed with merge, as follows:

;; (define S (cons-stream 1 (merge <??> <??>)))

;; Fill in the missing expressions in the places marked <??> above.

(define (scale-stream S n)
  (stream-map (lambda(x)(* n x)) S))

(define (merge s1 s2)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
         (let ((s1car (stream-car s1))
               (s2car (stream-car s2)))
           (cond ((< s1car s2car)
                  (cons-stream s1car (merge (stream-cdr s1) s2)))
                 ((> s1car s2car)
                  (cons-stream s2car (merge s1 (stream-cdr s2))))
                 (else
                  (cons-stream s1car
                               (merge (stream-cdr s1)
                                      (stream-cdr s2)))))))))

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

(newline)
(display (stream-ref S 1))(newline)
(display (stream-ref S 2))(newline)
(display (stream-ref S 3))(newline)
(display (stream-ref S 4))(newline)
(display (stream-ref S 5))(newline)
(display (stream-ref S 6))(newline)
(display (stream-ref S 7))(newline)
(display (stream-ref S 8))(newline)
(display (stream-ref S 9))(newline)
(display (stream-ref S 10))(newline)
(display (stream-ref S 11))(newline)
(display (stream-ref S 12))(newline)
(display (stream-ref S 13))(newline)
(display (stream-ref S 14))(newline)
(display (stream-ref S 15))(newline)
(display (stream-ref S 16))(newline)
(display (stream-ref S 17))(newline)

;; Output:
;Loading "sicp_prob_03.56.scm"...
;2
;3
;4
;5
;6
;8
;9
;10
;12
;15
;16
;18
;20
;24
;25
;27
;30
;... done

sicp exercise 3.55

;; Exercise 3.55.  Define a procedure partial-sums that takes as argument a stream S and returns the stream whose elements are S0, S0 + S1, S0 + S1 + S2, .... For example, (partial-sums integers) should be the stream 1, 3, 6, 10, 15, ....


(define (add-streams s1 s2)
  (stream-map + s1 s2))

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

(define integers (integers-from-n 1))

(define (partial-sum s)
  (define result (cons-stream (stream-ref s 0)
                              (add-streams (stream-cdr s) result)))
   result)


(newline)
(display (stream-ref (partial-sum integers) 0))(newline)
(display (stream-ref (partial-sum integers) 1))(newline)
(display (stream-ref (partial-sum integers) 2))(newline)
(display (stream-ref (partial-sum integers) 3))(newline)
(display (stream-ref (partial-sum integers) 4))(newline)

;; Output:
;Loading "sicp_prob_03.55.scm"...
;1
;3
;6
;10
;15
;... done

sicp exercise 3.54

;; Exercise 3.54.  Define a procedure mul-streams, analogous to add-streams, that produces the elementwise product of its two input streams. Use this together with the stream of integers to complete the following definition of the stream whose nth element (counting from 0) is n + 1 factorial:

;; (define factorials (cons-stream 1 (mul-streams <??> <??>)))

(define (mul-streams s1 s2)
  (stream-map * s1 s2))

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

(define integers (integers-from-n 1))

(define factorials (cons-stream 1 (mul-streams integers factorials)))

(display (stream-ref factorials 5))(newline)

sicp exercise 3.53

;; Exercise 3.53.  Without running the program, describe the elements of the stream defined by

;; (define s (cons-stream 1 (add-streams s s)))

(define (add-streams s1 s2)
  (stream-map + s1 s2))

(define s (cons-stream 1 (add-streams s s)))

(newline)
(display (stream-ref s 2)) (newline)
(display (stream-ref s 3)) (newline)
(display (stream-ref s 4)) (newline)
(display (stream-ref s 5)) (newline)
(display (stream-ref s 6)) (newline)
(display (stream-ref s 7)) (newline)

;; Output
; 4
; 8
; 16
; 32
; 64
; 128
;... done

sicp exercise 3.52

;; Exercise 3.52.  Consider the sequence of expressions

;; (define sum 0)
;; (define (accum x)
;;   (set! sum (+ x sum))
;;   sum)
;; (define seq (stream-map accum (stream-enumerate-interval 1 20)))
;; (define y (stream-filter even? seq))
;; (define z (stream-filter (lambda (x) (= (remainder x 5) 0))
;;                          seq))
;; (stream-ref y 7)
;; (display-stream z)

;; What is the value of sum after each of the above expressions is evaluated? What is the printed response to evaluating the stream-ref and display-stream expressions? Would these responses differ if we had implemented (delay <exp>) simply as (lambda () <exp>) without using the optimization provided by memo-proc ? Explain.


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

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

(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 sum 0)
(define (accum x)
  (set! sum (+ x sum))
  sum)
(define seq (stream-map accum (stream-enumerate-interval 1 20)))
(define y (stream-filter even? seq))
(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                         seq))
(newline)
(display (stream-ref y 7))(newline)
(display-stream z)(newline)
(display sum)(newline)

;; Output:
; 136
;
; 10
; 15
; 45
; 55
; 105
; 120
; 190
; 210
; 210
;... done

;; If the procedure (delay <exp>) is implemented as (lambda() <exp>) without the memo-proc, then everytime the stream is referenced, the #promise is evaluated again. If mem-proc is used, the #promise's earlier computed value is returned instead of evaluating the procedure again.

sicp exercise 3.51

;; Exercise 3.51.  In order to take a closer look at delayed evaluation, we will use the following procedure, which simply returns its argument after printing it:

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

;; What does the interpreter print in response to evaluating each expression in the following sequence?59

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


(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream low
                   (stream-enumerate-interval (+ 1 low) high))))
(define (stream-ref s n)
  (if (= n 0) (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

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

(define (show x)
  (display x)(newline)
    x)
(define x (stream-map show (stream-enumerate-interval 0 10)))
(display (stream-ref x 5))(newline)
(display (stream-ref x 7))(newline)

sicp exercise 3.50

;; Exercise 3.50.  Complete the following definition, which generalizes stream-map to allow procedures that take multiple arguments, analogous to map in section 2.2.3, footnote 12.

;; (define (stream-map proc . argstreams)
;;   (if (<??> (car argstreams))
;;       the-empty-stream
;;       (<??>
;;        (apply proc (map <??> argstreams))
;;        (apply stream-map
;;               (cons proc (map <??> argstreams))))))

(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream low
                   (stream-enumerate-interval (+ 1 low) 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)))))
(define (stream-ref s n)
  (if (= n 0) (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))
(define (stream-for-each proc s)
  (if (stream-null? s) 'done
      (begin (proc (stream-car s)) (stream-for-each proc (stream-cdr s)))))

(define (stream-map proc . argstreams )
  (if (stream-null? (car argstreams))
      the-empty-stream
      (cons-stream
        (apply proc (map stream-car argstreams))
        (apply stream-map
               (cons proc (map stream-cdr argstreams))))))
(define (add-streams s1 s2) (stream-map + s1 s2))

(define ones (cons-stream 1 ones))
(display (stream-ref ones 100))(newline)
(define fibs (cons-stream 0 (cons-stream 1 (add-streams (stream-cdr fibs) fibs))))
(display (stream-ref fibs 100))(newline)