#lang racket

;;; ---------------------------------------------------------------
;;; Helper functions

(define (curry2 binop)
  (λ (x) (λ (y) (binop x y))))

(define (flip2 f)
  (λ (x y) (f y x)))

(define ??? 42) ;; For partial defns with ??? in them 

;;; ---------------------------------------------------------------
;;; Factorial and Fibonacci

(define (fact-rec n)
  (if (= n 0)
      1
      (* n (fact-rec (- n 1)))))

(define (fact-iter n)
  (fact-tail n 1))

(define (fact-tail num ans)
  (if (= num 0)
      ans
      (fact-tail (- num 1) (* num ans))))

;;; How long does (fib-rec 40) take?
;;; (fib-rec 47)? (fib-rec 50)?
(define (fib-rec n)
  (if (< n 2)
      n
      (+ (fib-rec (- n 1)) (fib-rec (- n 2)))))

;;; How long does (fib-iter 40) take?
;;; (fib-iter 47)? (fib-iter 50)?
(define (fib-iter n)
  (fib-tail ???) ; Flesh out the arguments
  )

(define (fib-tail n i fib_i fib_i_plus_1)
  ;; Flesh out this body
  ???
  )

;;; ---------------------------------------------------------------
;;; Extremely silly and inefficient recursive incrementing function
(define (inc-rec n)
  (if (= n 0)
      1
      (+ 1 (inc-rec (- n 1)))))

(define (inc-iter n)
  (inc-tail n 1))

(define (inc-tail num resultSoFar)
  (if (= num 0)
      resultSoFar
      (inc-tail (- num 1) (+ resultSoFar 1))))

;;; ---------------------------------------------------------------
;;; foldl is like foldr excepts accumulates answer iteratively,
;;; left-to-right

(define (my-foldl combiner resultSoFar xs)
  (if (null? xs)
      resultSoFar
      (my-foldl combiner
                (combiner (first xs) resultSoFar)
                (rest xs))))

(define (whatisit f xs)
  (foldl (λ (x listSoFar)
           (cons (f x) listSoFar))
         null
         xs))

(define (reverse-iter xs)
  (foldl cons null xs))

(define (reverse-rec xs)
  (foldr snoc null xs))

(define (snoc x ys)
  (foldr cons (list x) ys))

;;; ---------------------------------------------------------------
;;; iterate abstracts over iterating with state variables

(define (iterate next done? finalize state)
  (if (done? state)
      (finalize state)
      (iterate next done? finalize (next state))))

(define (fact-iterate n)
  (iterate (λ (num&prod)
             (list (- (first num&prod) 1)
                   (* (first num&prod) (second num&prod))))
           (λ (num&prod) (<= (first num&prod) 0))
           (λ (num&prod) (second num&prod))
           (list n 1)))

(define (least-power-geq base threshold)
  (iterate ???  ; next
           ???  ; done?
           ???  ; finalize
           ???  ; initial state
           ))

(define (expt-of-least-power-geq base threshold)
  (iterate ???  ; next
           ???  ; done?
           ???  ; finalize
           ???  ; initial state
           ))

(define (mystery1 n) ; Assume n >= 0
  (iterate (λ (ns) (cons (- (first ns) 1) ns))
           (λ (ns) (<= (first ns) 0))
           (λ (ns) ns)
           (list n)))

(define (mystery2 n)
  (iterate (λ (ns) (cons (quotient (first ns) 2) ns))
           (λ (ns) (<= (first ns) 1))
           (λ (ns) (- (length ns) 1))
           (list n)))

(define (fact-let n)
  (iterate (λ (num&prod)
             (let ([num (first num&prod)]
                   [prod (second num&prod)])
                (list (- num 1) (* num prod))))
           (λ (num&prod) (<= (first num&prod) 0))
           (λ (num&prod) (second num&prod))
           (list n 1)))

(define (fact-match n)
  (iterate (λ (num&prod)
             (match num&prod
               [(list num prod)
                (list (- num 1) (* num prod))]))
           (λ (num&prod) (match num&prod [(list num prod) (<= num 0)]))
           (λ (num&prod) (match num&prod [(list num prod) prod]))
           (list n 1)))

;;; ---------------------------------------------------------------
;;; iterate-apply simplifies case of multiple state variables

(define (iterate-apply next done? finalize state)
  (if (apply done? state)
      (apply finalize state)
      (iterate-apply next done? finalize (apply next state))))

(define (fact-iterate-apply n)
  (iterate-apply
   (λ (num prod) (list (- num 1) (* num prod)))
   (λ (num prod) (<= num 0))
   (λ (num prod) prod)
   (list n 1)))

(define (fib-iterate-apply n)
 (iterate-apply ???  ; next
		???  ; done?
                ???  ; finalize
                ???  ; initial state
                ))

;;; ---------------------------------------------------------------
;;; iterative versions of genlist and genlist-apply

(define (genlist-iter next done? keepDoneValue? seed)
  (iterate-apply
   (λ (state reversedStatesSoFar)
     (list (next state) (cons state reversedStatesSoFar)))
   (λ (state reversedStatesSoFar) (done? state))
   (λ (state reversedStatesSoFar) 
     (if keepDoneValue?
         (reverse (cons state reversedStatesSoFar))
         (reverse reversedStatesSoFar)))
   (list seed '())))
     
(define (halves-iter num)
  (genlist-iter (λ (n) (quotient n 2))
                (λ (n) (<= n 0))
                #t
                num))

(define (my-range-iter lo hi)
  (genlist-iter (λ (n) (+ n 1))
                (λ (n) (>= n hi))
                #f
                lo))

(define (my-range-step-iter lo hi step)
  (genlist-iter (λ (n) (+ n step))
                (λ (n) (>= n hi))
                #f
                lo))

(define (genlist-apply-iter next done? keepDoneValue? seed)
  (iterate-apply
   (λ (state reversedStatesSoFar)
     (list (apply next state) (cons state reversedStatesSoFar)))
   (λ (state reversedStatesSoFar) (apply done? state))
   (λ (state reversedStatesSoFar) 
     (if keepDoneValue?
         (reverse (cons state reversedStatesSoFar))
         (reverse reversedStatesSoFar)))
   (list seed '())))

(define (fact-table-apply-iter n)
  (genlist-apply-iter
   (λ (num ans) (list (- num 1) (* num ans)))
   (λ (num ans) (<= num 0))
   #t 
   (list n 1)))