;;; streams.scm

;;  although the title above refers only to streams
;;  in reality this file compares lists with streams
;;  lists are sequences of nested dotted pairs
;;     an item and a reference to the rest of the list
;;     terminating with the empty list
;;  streams are sequences of nested dotted pairs
;;     an item and a promise for the rest of the list
;;     terminating with a promise to the empty list

;;  streams are commonly referred to as delayed list

;;  streams have the potential to define
;;     infinitely long lists

;; empty list and empty streams
(define the-empty-list '())
(define the-empty-stream '())

(define list-null? null?)
(define stream-null? null?)

;; list basics operations
(define list-cons cons)
(define list-first first)
(define list-car first)
(define list-rest rest)
(define list-cdr rest)

;; stream basic operations
(define stream-cons (macro (x y)
  `(cons ,x (delay ,y)) ))
(define stream-first first)
(define stream-car first)
(define stream-rest (macro (streamx)
  `(force (rest ,streamx)) ))
(define stream-cdr stream-rest)

;; list and stream creation
(define stream (macro args
  (if (null? args)
      '()
      `(stream-cons ,(car args) (stream ,@(cdr args))) ) ))

;; list and stream components
(define list-pair? pair?)
(define stream-pair? (lambda (item)
  (and (pair? item)
       (promise? (cdr item)) ) ))

;; list-index and stream-index
(define list-index (lambda (listx item)
  (if (list-null? listx)
      'error
      (if (eqv? item (list-car listx))
          0
          (+ 1 (list-index
                  (list-cdr listx) item)) ) ) ))
(define stream-index (lambda (streamx item)
  (if (stream-null? streamx)
      'error
      (if (eqv? item (stream-car streamx))
          0
          (+ 1 (stream-index
                  (stream-cdr streamx) item)) ) ) ))

;; list-ref and stream-ref
(define list-ref (lambda (listx n)
  (if (< n 0)
      'error
      (if (= n 0)
          (list-car listx)
          (list-ref (list-cdr listx) (- n 1)) ) ) ))
(define stream-ref (lambda (streamx n)
  (if (< n 0)
      'error
      (if (= n 0)
          (stream-car streamx)
          (stream-ref (stream-cdr streamx) (- n 1)) ) ) ))

;; the following handful of lines of code are
;;    of great concern to me!
;; the quote-it lambda form is defined solely
;;    to allow the apply primitive
;; to execute properly on the list-to-stream conversion
;; it is a kludge to make one section of code
;;    behave properly (not a good practice!!)

;; the deeper underlying issue has to do with apply
;;    - is apply a lambda form??
;;         and evaluates all its arguments
;;    - is apply a macro form??
;;         and does not evaluate

(define quote-it (lambda (item)
  (cons 'quote (cons item '())) ))

;; list-to-stream and stream-to-list conversions
(define list->stream (macro (listx)
  `(apply stream (map quote-it ,listx)) ))
(define stream->list (lambda (streamx)
  (if (null? streamx)
      '()
      (list-cons (stream-car streamx)
                 (stream->list (stream-cdr streamx))) ) ))

;;; introduction to infinite streams

(define const-next (macro (a)
  `(stream-cons ,a (const-next ,a)) ))
(define ones (const-next 1))
(define twos (const-next 2))
(define threes (const-next 3))

(define integers-starting-from (macro (n)
  `(stream-cons ,n (integers-starting-from ,(+ n 1))) ))
(define nats (integers-starting-from 1))

(define alt-next (macro (a)
  `(stream-cons ,a (alt-next ,(- a))) ) )
(define alts (alt-next 1))

(define fib-next (macro (a b)
  `(stream-cons ,a (fib-next ,b (+ ,a ,b))) ) )

(define fibs (fib-next 1 1))

;;; at present my implementation of skeme
;;; does not like recursive definitions for streams

(define recursive-ones (stream-cons 1 recursive-ones))

; (stream-ref recursive-ones 17)
; (stream-ref recursive-ones 23)

; both will work fine,
;    but only after forcing the recursive promise
; a simple eval will cause a stack overflow
;    due to infinite recursion.