;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname lect26-tail-recursion-loops) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ())))

;;;;;;;;;;;;;;;;;;;;;;;;; fold ;;;;;;;;;;;;;;;;;;;;;;;

;;;;;;
#|
(check-expect (my-max (cons 4 (cons 7 empty))) 7)

(check-expect (my-max (cons 4 (cons 7 empty))) 7)

|#





; foldr : (string, string -> string),  string, list-of-string -> string
;
(define (fold combine base data)
  (cond [(empty? data)  base]
        [(cons? data)   (combine (first data)
                                 (fold combine base (rest data)))]))


; We can now write, say:
;
(fold (lambda (f rr) (string-append f " " rr))
      "whoa"
      (list "hi" "bye" "aloha" "'Tag" "bueno"))


; Self-check:
;  - Write `my-reverse` yourself, using the template.
;    You'll find that you want a helper-function;
;     - write that helper using the template.
;     - write that helper using `fold`.
;  - Write `my-reverse`, using `fold` (and calling your helper-function).
;  - For fun: can you write the whole thing, w/o ever naming your helper function?

(define (make-adder k)
  (λ (n) (+ k n)))






; Here's an equivalent 'spelled out' version which uses the template:
; HOWEVER, we are now realizing that it builds up many stack frames
; (as demo'd in the stepper):


; Let's write the following function `string-append-whoa`:
;
(check-expect (string-append-whoa  (list "hi" "bye" "aloha"))
              "hi bye aloha whoa")


; string-append-whoa : list-of-strings -> string
;
(define (string-append-whoa strs)
  (cond [(empty? strs) "whoa"]
        [(cons? strs)  (string-append (first strs)
                                      " "
                                      (string-append-whoa (rest strs)))]))


#|  // Java loop version of the above:
    //
String stringAppendWhoa( List<String> strs ) {  
  String resultSoFar = "whoa";
  while (!strs.isEmpty()) {
    resultSoFar = strs.get(0) + " " + resultSoFar;
    strs = strs.sublist(1);
    }
  return resultSoFar;
  }
    // Why doesn't this loop build up stack frames?
    // Because the `while` turns into
    // a "goto start of loop, with revised `resultSoFar` and `strs`."
|#

; If we also use a 'so-far' variable, then we can
; write a racket version which doesn't build up stack-frames:

(check-expect (string-append-whoa2  (list "hi" "bye" "aloha"))
              "hi bye aloha whoa")



(define (string-append-whoa2 strs)
  (saw2-help (reverse strs) "whoa"))

(define (saw2-help strs result-so-far)
  (cond [(empty? strs) result-so-far]
        [(cons? strs) (saw2-help (rest strs)
                                 (string-append (first strs) " " result-so-far))]))

; To achieve tail-recursion, we used the trick:
; add an "accumulator" variable (or, a "so-far" variable).

; A function is 'tail recursive' if its recursive call is the last thing it
; needs to do.
; (It doesn't need to combine the *results* of the recursive call in any way.)
; If a language implements tail-recursion, it won't build up stack frames
; for TAIL-recursive calls.
           
; Scheme (racket): required to implement tail-recursion.
; Java : cannot implement tail recursion (the jvm spec doesn't allow it, and 
;            Java must be backwards-compatible).




;;;;;;;;;;
;; Loops in scheme:


; There isn't a 'while' loop built in.
; Can we write our own, as a function?
; How would we call it?

(check-expect (nums-down-from 7)
              (list 7 6 5 4 3 2 1))
;(sqrts-down-from 17) = (list 4.101 4 3.98 ... 1.414 1)

(define (nums-down-from n)
  (while/list positive? n sub1))

(check-expect (while/list cons? (list "a" "b" "c") rest)
              (list  (list "a" "b" "c")
                     (list "b" "c")
                     (list "c")))

; while/list:  (α -> boolean), α, (α -> α)  ->  (list-of α)
; Return a list containing `indx`, `(update indx)`, `(update (update indx))`, ...
; so long as `continue?` of that quantity returns true.
;
(define (while/list continue? indx update)
  (reverse (wl-help continue? indx update empty)))




; wl-help :
; Return a list containing `indx`, `(update indx)`, `(update (update indx))`, ...
; so long as `continue?` of that quantity returns true --
; all prepended to the front of `results-so-far`.
; 
(define (wl-help continue? indx update result-so-far)
  (cond [(continue? indx)
         (wl-help continue? (update indx) update (cons indx result-so-far))]
        [else result-so-far]))
     
; Q1: Call while/list to count from 10 to (but not including) 20.

(while/list (λ (k) (< k 20))
            10
            (λ (n) (+ n 1)))
;
; Q2: Write the function 'nums-from-to',
;     whose body is just a single call to `while/list`.
;
; Q3: Write `for/list`, which takes a start, stop, and body
;     and returns a list of all the body-results.
;      i. Implement this w/o calling any of the functions above
;     ii. What's the cheapo way of writing this, using functions above?