(load "./srfi-40.scm")

(print "* basic streams")
(let ((s (stream-from-to 10 15)))
  (stream-for-each print s)
  (stream-for-each print (stream-map sqrt s)))

(define (prime? number)
  (call/cc
   (lambda (return)
     (do ((i 2 (+ i 1)))
         ((> i (sqrt number)) #t)
       (when (= (modulo number i) 0)
         (return #f))))))

(define prime-list
  (stream-filter prime? (stream-from-to 1 1000)))

(define fact-list
  (let fact ((a 1) (n 1))
    (stream-cons a (fact (* a n) (+ n 1)))))

(define fib-list
  (let fib ((fib-2 0) (fib-1 1))
    (stream-cons fib-1 (fib fib-1 (+ fib-2 fib-1)))))

(print (stream-ref fact-list 10))
(print (stream-ref fib-list 10))
(print (stream->list (stream-take 10 fact-list)))
(print (stream->list (stream-take 10 fib-list)))

;; integers I
(print "* integers I")
(define ones (stream-cons 1 ones))
(define (add-streams s1 s2)
  (stream-map + s1 s2))

;; alternative
;; (define (add-streams s1 s2)
;;   (let ((h1 (head s1))
;;         (h2 (head s2)))
;;     (stream-cons
;;      (+ h1 h2)
;;      (add-streams (tail s1) (tail s2)))))

(define integers (stream-cons 1 (add-streams ones integers)))
(print (stream->list (stream-take 20 ones)))
(print (stream->list (stream-take 20 integers)))

;; integers II
(print "* integers II")
(define (integers-starting-from n)
  (stream-cons n (integers-starting-from (+ n 1))))
(define integers (integers-starting-from 1))
(print (stream->list (stream-take 20 integers)))

;; integers III
(print "* integers III")
(define integers
  (let int ((n 1))
    (stream-cons n (int (+ n 1)))))
(print (stream->list (stream-take 20 integers)))

;; deep magic: mutually recursive definition
(print "* primes")
(define primes
  (stream-cons
   2
   (stream-filter prime? (integers-starting-from 3))))

(define (prime? n)
  (define (square x) (* x x))
  (define (divisible? x y) (= 0 (modulo x y)))
  (define (iter ps)
    (cond ((> (square (stream-car ps)) n) #t)
          ((divisible? n (stream-car ps)) #f)
          (else (iter (stream-cdr ps)))))
  (iter primes))

(print (stream->list (stream-take 20 primes)))

(print "* prime forms")
(define (find-prime-forms . args)
  ;; TODO read form:
  ;; Enter an expression in terms of N: (1+ (* n n))
  ;; Primes of the form (1+ (* n n)):
  ;; n=0, p=1
  ;; ...
  (let loop ((form (lambda (n)
                     (+ 1 (* n n))))
             (i 1)
             (maximum 1000)
             (hits 0)
             (result ()))
    (cond ((= i maximum)
           (format #t "found ~d primes of this form for 0<=N<1000\n" hits)
           (reverse result))
          ((prime? (form i))
           (inc! hits)
           (loop form (+ i 1) maximum hits (cons (cons i (form i)) result)))
          (else
           (loop form (+ i 1) maximum hits result)))))

(find-prime-forms)

(define-macro (create-closure form)
  `(lambda (n)
     ,(eval form (current-module))))

;; haskell primes
;; primes		:: Integral a => [a]
;; primes		= map head (iterate sieve [2..])
;; sieve (p:xs)	= [ x | x<-xs, x `rem` p /= 0 ]
;;
;; -- elem function with upper bound n
;; elemof		:: Ord a => a -> [a] -> Bool
;; elemof n xs	= elem n (takeWhile (<=n) xs)
;;
;; mersenne	= [ n | n<-primes, (2^n-1) `elemof` primes ]

;; -- iterate f x returns an infinite list of repeated applications of f to x:
;; -- iterate f x == [x, f x, f (f x), ...]
;; iterate          :: (a -> a) -> a -> [a]
;; iterate f x      =  x : iterate f (f x)

(define head stream-car)
(define tail stream-cdr)

(define (iterate f x)
  (stream-cons x (iterate f (f x))))

(define (nofactor m n)
  (not (= (remainder m n) 0)))

;; (define (sieve stream)
;;   (stream-filter (lambda (p)
;;                    (nofactor (head (tail stream)) p))
;;                    ;;(not (= (remainder x (stream-car stream)) 0)))
;;                  stream))

;; alternate approach (see below)
(define (remove-multiples n stream)
  (if (nofactor (head stream) n)
      (stream-cons (head stream)
                   (remove-multiples n (tail stream)))
      (remove-multiples n (tail stream))))

(define (sieve stream)
  (stream-cons (head stream)
               (sieve (remove-multiples (head stream) (tail stream)))))

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

;; (define primes
;;   (stream-map head (iterate sieve (integers-starting-from 2))))

;; see also:
;; http://www.cs.auc.dk/~normark/prog3-02/html/notes/
;;        eval-order_themes-delay-stream-section.html

(define (sieve stream)
  (stream-cons
   (head stream)
   (sieve
    (stream-filter
     (lambda (x) (not (divisible? x (head stream))))
     (tail stream)))))

(define (divisible? x y)
  (= (remainder x y) 0))

;; (define (filter-stream p lst)
;;   (cond ((stream-null? lst) the-empty-stream)
;;         ((p (head lst)) (stream-cons (head lst)
;;                                      (filter-stream p (tail lst))))
;;         (else (filter-stream p (tail lst)))))

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

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

;; 6. Implementation
;; nofactor :: Integer -> Integer -> Bool
;; nofactor m n = rem n m /= 0
;; nofactors :: Integer -> Integer -> Bool
;; nofactors m n | m^2 > n
;; = True
;; | otherwise = nofactor m n
;; && nofactors (m+1) n
;; prime :: Integer -> Bool
;; prime n | n < 1
;; = error "not a positive integer"
;; | n == 1
;; = False
;; | otherwise = nofactors 2 n
;; 7. Trying it out
;; somePrimes :: [Integer]
;; somePrimes = [ x | x <- [1..1000], prime x ]
;; primesUntil :: Integer -> [Integer]
;; primesUntil n = [ x | x <- [1..n], prime x ]
;; allPrimes :: [Integer]
;; allPrimes = [ x | x <- [1..], prime x ]
;; GSWH> primesUntil 50
;; [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
;; GSWH>

(define  (interval-list m n)
  (if (> m n)
      '()
      (cons m (interval-list (+ 1 m) n))))

(define (sieve l)
  (define (remove-multiples n l)
    (if (null? l)
        '()
        (if  (= (modulo (car l) n) 0)      ; division test
             (remove-multiples n (cdr l))
             (cons (car l)
                   (remove-multiples n (cdr l))))))

  (if (null? l)
      '()
      (cons (car l)
            (sieve (remove-multiples (car l) (cdr l))))))

(define (primes<= n)
  (sieve (interval-list 2 n)))

;; (primes<= 300)