(load "./stream")
(import stream)

(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 2)))

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

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

(print (stream-cutoff 10 prime-list))
(print (stream-cutoff 10 factorial-list))
(print (stream-cutoff 10 fibonacci-list))
(print (stream->list (stream-take 10 factorial-list)))
(print (stream-ref prime-list 10))
(stream-for-each (lambda (x) (print x)) (stream-take 5 prime-list))
(print (stream->list (list->stream '(1 2 3 4 5))))
(print (stream-cutoff 20 (stream-iterate cos 4)))

(call-with-input-file "/etc/passwd"
  (lambda (port)
    (let loop ((s (port->stream read-line port)))
      ;;(format #t "~s\n" (stream->list s))
      (cond
       ((stream-null? s) 'ok)
       (else
        (print (stream-car s))
        (loop (stream-cdr s)))))))

(exit)

;; enumerate the first 10 even cubes
(let ((even? (lambda (x)
               (= (modulo x 2) 0)))
      (cube (lambda (x)
              (* x x x))))
  (stream->list
   (stream-take 10
                (stream-filter even?
                               (stream-map cube (stream-from 1))))))

;; 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)))

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

;; integers III
(define integers
  (let int ((n 1))
    (stream-cons n (int (+ n 1)))))

;; deep magic: mutually recursive definition
(define primes
  (stream-cons 2 (stream-filter prime? (stream-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))

(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)))))

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

;; -----------------------------------------------------------------
;; -----------------------------------------------------------------
;; -----------------------------------------------------------------
;; a bunch of prime implementations

;; 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
    (filter-stream
     (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)