#lang racket

(require "stream-base.rkt")

; stream examples

; seiving the primes

; a function that recursively generates an stream of integers starting
; at n
(define (integers-starting-from n)
  (s-cons n (integers-starting-from (+ n 1))))

; the natural numbers
(define naturals (integers-starting-from 0))

; true if a divides b evenly
(define (divides? a b) (= (remainder b a) 0))

; true if x is evenly divisible by y
(define (divisible? x y) (= (remainder x y) 0))

; sieve of Eratosthenes for generating primes
; (seive s) is the first term f of s followed by all the remaining terms
; that are not divisible by f.  Composing f with a seive on the rest
; then filters out the next prime, and so on.

; If s does not contain any integers that are divisible by an integer
;   < (s-first s)
; then the rest of this stream
;   (s-filter (lambda (x) (not (divisible? x (s-first s)))) (s-rest s))
; does not contain any integers that are divisible by an integer < it's
; first element.

(define (sieve s)
  (s-cons (s-first s)
    ; filter out all the multiples of (s-first s) from the rest of the list
    ; then feed it into the sieve to get the new stream
    (sieve (s-filter 
                (lambda (x) (not (divisible? x (s-first s))))
                (s-rest s))
          )
    ))

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

; try 
; (print primes)
; (s-ref primes 1)
; (s-ref primes 5)
; (print primes)