sicp-3-5-2-infinite-streams

#lang racket
(require "sicp-3-5-streams.rkt") ; for all the book code from 3.5.1 and 3.5.2

;;;;;;;;;;
;; 3.53 ;;
;;;;;;;;;;

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

(define (display-ten s)
  (for ([i 10])
    (printf "~a " (my-stream-ref s i)))
  (printf "~n"))

(display-ten powers) ; should be 1 2 4 8 etc
;; 1 2 4 8 16 32 64 128 256 512

;;;;;;;;;;
;; 3.54 ;;
;;;;;;;;;;

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

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

(display-ten factorials)
;; 1 1 2 6 24 120 720 5040 40320 362880

;;;;;;;;;;
;; 3.55 ;;
;;;;;;;;;;

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

(display-ten (partial-sums integers))
;; 1 3 6 10 15 21 28 36 45 55

;;;;;;;;;;
;; 3.56 ;;
;;;;;;;;;;

(define (merge s1 s2)
  (cond [(stream-null? s1) s2]
        [(stream-null? s2) s1]
        [else
          (define s1car (stream-car s1))
          (define 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 hamming
  (cons-stream 1
               (merge (scale-stream hamming 2)
                      (merge (scale-stream hamming 3)
                             (scale-stream hamming 5)))))

(display-ten hamming)
;; 1 2 3 4 5 6 8 9 10 12

;; Let's look at the first ten >= 100.

(display-ten (my-stream-filter (lambda (x) (>= x 100)) hamming))
;; 100 108 120 125 128 135 144 150 160 162

;;;;;;;;;;
;; 3.57 ;;
;;;;;;;;;;

(define (count-fibs n)
  (define num 0)
  (define (plus a b)
    (set! num (add1 num))
    (+ a b))
  (define (count-add-streams s1 s2)
    (my-stream-map plus s1 s2))
  (define fib-stream
    (cons-stream 0
                 (cons-stream 1
                              (count-add-streams (stream-cdr fib-stream)
                                                 fib-stream))))
  (define result (my-stream-ref fib-stream n))
  (printf "~a ~a ~a ~n" n result num)
  result)

;; MEMOIZED

(for ([i 20]) (count-fibs i))
;;   n    result number of additions
;;   0    0      0
;;   1    1      0
;;   2    1      1
;;   3    2      2
;;   4    3      3
;;   5    5      4
;;   6    8      5
;;   7    13     6
;;   8    21     7
;;   9    34     8
;;   10   55     9
;;   11   89     10
;;   12   144    11
;;   13   233    12
;;   14   377    13
;;   15   610    14
;;   16   987    15
;;   17   1597   16
;;   18   2584   17
;;   19   4181   18

;; NOT MEMOIZED

;;   n    result number of additions
;;   0    0      0
;;   1    1      0
;;   2    1      1
;;   3    2      3
;;   4    3      7
;;   5    5      14
;;   6    8      26
;;   7    13     46
;;   8    21     79
;;   9    34     133
;;   10   55     221
;;   11   89     364
;;   12   144    596
;;   13   233    972
;;   14   377    1581
;;   15   610    2567
;;   16   987    4163
;;   17   1597   6746
;;   18   2584   10926
;;   19   4181   17690

;; Note that the number of additions, and thus the time complexity, is almost
;; doubling each time.  That is because un-memoized recursive fibonacci is
;; O(phi ^ n) as we learned in exercise 1.31.

;;;;;;;;;;
;; 3.58 ;;
;;;;;;;;;;

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

(display-ten (expand 1 7 10)) ; 1 / 7 = 0.1428571428...
;; 1 4 2 8 5 7 1 4 2 8

(display-ten (expand 3 8 10)) ; 3 / 8 = 0.375
;; 3 7 5 0 0 0 0 0 0 0

;; Expand produces the digits in the base radix expansion of num / den.

;;;;;;;;;;
;; 3.59 ;;
;;;;;;;;;;

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

(define exp-series
  (cons-stream 1 (integrate-series exp-series)))

(display-ten exp-series) ; should be 1 / n!
;; 1 1 1/2 1/6 1/24 1/120 1/720 1/5040 1/40320 1/362880

(define cosine-series ; derivative of cosine is -1 * sine
  (cons-stream 1 (scale-stream
                   (integrate-series sine-series)
                   -1)))

(define sine-series ; derivative of sine is cosine
  (cons-stream 0 (integrate-series cosine-series)))

(display-ten cosine-series) ; 2 * n term should be (-1) ^ n / (2 * n)!
;; 1 0 -1/2 0 1/24 0 -1/720 0 1/40320 0

(display-ten sine-series) ; 2 * n + 1 term should be (-1) ^ n / (2 * n + 1)!
;; 0 1 0 -1/6 0 1/120 0 -1/5040 0 1/362880

;;;;;;;;;;
;; 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 s2 (stream-cdr s1)))))

;; The idea is:
;; (a0 + a1 * x + a2 * x ^ 2 + ...) * (b0 + b1 * x + b2 * x ^ 2 + ...)
;; = a0 * (b0 + b1 * x + b2 * x ^ 2 + ...)
;; + (a1 * x + a2 * x ^ 2 + ...) * (b0 + b1 * x + b2 * x ^ 2 + ...)

(display-ten (add-streams (mul-series cosine-series cosine-series)
                          (mul-series sine-series sine-series)))
;; 1 0 0 0 0 0 0 0 0 0

(display-ten (mul-series integers integers)) ; should be 1 4 10 20 35 etc
;; 1 4 10 20 35 56 84 120 165 220

;;;;;;;;;;
;; 3.61 ;;
;;;;;;;;;;

(define (invert-unit-series s)
  (unless (= (stream-car s) 1)
    (error "Constant term must be 1 -- INVERT-UNIT-SERIES" s))
  (cons-stream 1
               (scale-stream (mul-series (stream-cdr s)
                                         (invert-unit-series s))
                             -1)))

(display-ten (invert-unit-series ones))
;; 1 -1 0 0 0 0 0 0 0 0

;; This says that the sum of the geometric series 1 + x + x ^ 2 + x ^ 3 + ...
;; = 1 / (1 - x) but expressed with inverses.

;;;;;;;;;;
;; 3.62 ;;
;;;;;;;;;;

(define (div-series s1 s2)
  (when (zero? (stream-car s2))
    (error "Constant term of second series must be non-zero -- DIV-SERIES" s2))
  (scale-stream
    (mul-series s1
                (invert-unit-series (scale-stream s2
                                                  (/ 1 (stream-car s2)))))
    (stream-car s2)))

(define tangent-series (div-series sine-series cosine-series))

(display-ten tangent-series) ; should be 0 1 0 1/3 0 2/15 0 17/315 etc
;; 0 1 0 1/3 0 2/15 0 17/315 0 62/2835