;;; Streams

;;; API of streams
;;;  - like lists:
;;;    - might be empty
;;;    - if not,
;;;      - has 1st element (like car of list)
;;;      - has stream of remaining elements (like cdr list)
;;;  - unlike lists:
;;;    - unbounded in length
;;;    - revealed in a lazy fashion, i.e., demand driven
;;;  - implementation:
;;;    - use lambda to create functions represent deferred computation

;;; prefix all stream-related functions with "stream-"

;;; represent a stream using an (potentially anonymous) function,
;;; using two function: stream-car, stream-cdr.

;;; internally, the function representing a stream can be called with 1 argument,
;;; which is a "selector", one of two symbols: car or cdr.

(define stream-car
  (lambda (stream)
    (stream 'car)))

(define stream-cdr
  (lambda (stream)
    (stream 'cdr)))

(define stream-of-1s
  (lambda (s)
    (cond ((eq? s 'car) 1)		; first elt of stream
	  ((eq? s 'cdr) stream-of-1s)	; remainder of stream
	  (else (error "invalid invocation")))))

;;; get first n elements of stream as list

(define stream-take
  (lambda (n stream)
    (if (zero? n)
	null
	(cons (stream-car stream)
	      (stream-take (- n 1) (stream-cdr stream))))))

(define stream-naturals
  (lambda (s)
    (cond ((eq? s 'car) 0)		; first elt of stream
	  ((eq? s 'cdr) (stream-map (lambda (x) (+ x 1))
				    stream-naturals))	; remainder of stream
	  (else (error "invalid invocation")))))

(define stream-map
  (lambda (f stream)
    (lambda (s)
      (cond ((eq? s 'car) (f (stream-car stream))) ; first elt of stream
	    ((eq? s 'cdr) (stream-map f (stream-cdr stream))) ; remainder of stream
	    (else (error "invalid invocation"))))))

(define fibb
  (lambda (n)
    (cond ((= n 0) 1)
	  ((= n 1) 1)
	  (else (+ (fibb (- n 1))
		   (fibb (- n 2)))))))

(define stream-of-fibbs-v1
  (stream-map fibb stream-naturals))

(define stream-+
  (lambda (stream1 stream2)
    (lambda (s)
      (cond ((eq? s 'car) (+ (stream-car stream1)
			     (stream-car stream2))) ; first elt of stream
	    ((eq? s 'cdr) (stream-+ (stream-cdr stream1)
				    (stream-cdr stream2))) ; remainder of stream
	    (else (error "invalid invocation"))))))

;;; stream-cons takes a 1st element & a "thunk" that produces the remainder
;;; of the stream.
;;; E.g., invoke with: (stream-cons 17 (lambda () stream))
(define stream-cons
  (lambda (x stream-thunk)
    (lambda (s)
      (cond ((eq? s 'car) x)		  ; first elt of stream
	    ((eq? s 'cdr) (stream-thunk)) ; remainder of stream
	    (else (error "invalid invocation"))))))

;; > (stream-take 20 (stream-map fibb stream-naturals))
;; (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)
;; > (stream-take 20 (stream-cdr (stream-map fibb stream-naturals)))
;; (1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946)

;;   (1 1 2 3  5  8 13 21 34 55  89 144 233 377 610  987 1597 2584 4181  6765)
;; + (1 2 3 5  8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946)
;; --------------------------------------------------------------------------
;;   (2 3 5 8 13 21 ... )

(define stream-of-fibbs
  (stream-cons 1
	       (lambda ()
		 (stream-cons 1
			      (lambda ()
				(stream-+ stream-of-fibbs
					  (stream-cdr stream-of-fibbs)))))))

;;; Q: are there more natural numbers than even numbers?
;;; A: no, card(Nat) = card(Even)

;;; Proof: construct bijection

;;; Nat = (0 1 2 3 4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 ...)
;;; Even= (0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 ...)


(define stream-qq
  (stream-map (lambda (num)
		(stream-map (lambda (den) (/ num den))
			    stream-pos))
	      stream-pos))

;; > (map (lambda (str) (stream-take 10 str)) (stream-take 10 stream-qq))
;; ((1 1/2 1/3 1/4 1/5 1/6 1/7 1/8 1/9 1/10)
;;  (2   1 2/3 1/2 2/5 1/3 2/7 1/4 2/9 1/5)
;;  (3 3/2   1 3/4 3/5 1/2 3/7 3/8 1/3 3/10)
;;  (4   2 4/3   1 4/5 2/3 4/7 1/2 4/9 2/5)
;;  (5 5/2 5/3 5/4 1 5/6 5/7 5/8 5/9 1/2)
;;  (6   3   2 3/2 6/5 1 6/7 3/4 2/3 3/5)
;;  (7 7/2 7/3 7/4 7/5 7/6 1 7/8 7/9 7/10)
;;  (8   4 8/3   2 8/5 4/3 8/7 1 8/9 4/5)
;;  (9 9/2   3  9/4 9/5 3/2 9/7 9/8 1 9/10)
;;  (10  5 10/3 5/2 2 5/3 10/7 5/4 10/9 1))

(define stream-zip
  (lambda (stream1 stream2)
    (stream-cons (stream-car stream1)
		 (lambda ()
		   (stream-zip stream2
			       (stream-cdr stream1))))))

;; > (stream-take 20 (stream-zip stream-of-1s (stream-map (lambda (x) 0) stream-of-1s)))
;; (1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0)

;; > (stream-take 20 (stream-zip stream-of-1s stream-of-fibbs))
;; (1 1 1 1 1 2 1 3 1 5 1 8 1 13 1 21 1 34 1 55)