#lang racket

(require csc151)
(require racket/match)
(require racket/undefined)
(require rackunit)

;; CSC 151-01 (Fall 2021)
;; Lab: Tail and Helper Recursion
;; Authors: YOUR NAMES HERE
;; Date: THE DATE HERE
;; Acknowledgements:
;;   ACKNOWLEDGEMENTS HERE

; +---------------+--------------------------------------------------
; | Provided code |
; +---------------+

;;; (num-sum number) -> number?
;;;   numbers : listof number?
;;; Find the sum of all the values in numbers
(define new-sum
  (lambda (numbers)
    (new-sum-helper 0 numbers)))

;;; (num-sum-helper sum-so-far remaining) -> number?
;;;   sum-so-far : number?
;;;   remaining : listof number?
;;; Find the sum of sum-so-far plus all the values
;;; in numbers.
(define new-sum-helper
  (lambda (sum-so-far remaining)
     (displayln (list 'helper sum-so-far remaining))
     (if (null? remaining)
         sum-so-far
         (new-sum-helper (+ sum-so-far (car remaining))
                         (cdr remaining)))))

;;; (furthest-from-zero numbers) -> real?
;;;   numbers : listof real?
;;; Determine the element in numbers which is furthest from
;;; zero (that is, has the largest value)
(define furthest-from-zero
  (lambda (numbers)
    (letrec ([helper
              (lambda (furthest-so-far remaining)
                ; (displayln (list 'helper furthest-so-far remaining))
                (if (null? remaining)
                    furthest-so-far
                    (helper (further-from-zero furthest-so-far 
                                               (car remaining))
                            (cdr remaining))))])
      (helper (car numbers) (cdr numbers)))))

;;; (further-from-zero val1 val2) -> real?
;;;   val1 : real?
;;;   val2 : real?
;;; Determine which of val1 and val2 is further from zero.
(define further-from-zero
  (lambda (val1 val2)
    ; (displayln (list 'further-from-zero val1 val2))
    (if (>= (abs val1) (abs val2))
        val1
        val2)))

;;; An alternate version of furthest-from-zero
(define furthest-from-zero/alt
  (lambda (numbers)
    (displayln (list 'furthest-from-zero/alt numbers))
    (if (null? (cdr numbers))
        (car numbers)
        (if (>= (abs (car numbers)) 
                (abs (furthest-from-zero/alt (cdr numbers))))
            (car numbers)
            (furthest-from-zero/alt (cdr numbers))))))

#| AB |#

; +-------------------------+----------------------------------------
; | Exercise 0: Preparation |
; +-------------------------+

#|
a. Have the normal start-of-lab discussion.  Consider strengths,
weaknesses, working styles, etc.
|#

#|
b. Discuss the self checks with your partner.
|#

#|
c. Review the purposes of the procedures above.
|#

#| A |#

; +---------------------------+--------------------------------------
; | Exercise 1: A quick trace |
; +---------------------------+

#|
`num-sum-helper` (above) is intended to give a quick trace of
its own behavior.  Verify that it does with a few examples.

TODO: Paste your examples from the interactions pane here.
|#

; +--------------------------------+---------------------------------
; | Exercise 2: Tracing, revisited |
; +--------------------------------+

#| 
a. Trace at a high level a call to 
  (furthest-from-zero (list -3 5 6 -2 1 -5))
Your sketch should start something like the following.

    (furthest-from-zero '(-3 5 6 -2 1 -5))
--> (helper -3 '(5 6 -2 1 -5))
--> (helper (further-from-zero -3 5) '(6 -2 1 -5))
--> (helper 5 '(6 -2 1 -5))
--> ...

<TODO: Finish that trace>
|#

#|
b. Uncomment the calls to `displayln` in those two procedures
so that you can have them trace themselves.
|#

#|
c. Evaluate the expression in DrRacket to see if you get a similar
trace.  (You won't see the nesting.)

<TODO: Post the trace here.>
|#

#| B |#

; +------------------------------+-----------------------------------
; | Exercise 3: Tallying numbers |
; +------------------------------+

#|
You may recall that in the past, you wrote a procedure, `tally-numbers`,
that took as input a list of mixed values (both numbers and
non-numbers) and returned a count of the number of numbers in the
list.

We will be rewriting `tally-numbers` using helper recursion.  The
helper procedure will likely have two parameters: a count of all
the numbers you've seen so far and a list of all the values you
have left to look at.
|#

#|
a.  Complete the following table, which represents what we 
expect to see at every step evaluating the helper on the list 
`'(5 a b 1 c 2 3 b 4)`.

        tally-so-far                    remaining
        ------------                    ---------
        0                               '(5 a b 1 c 2 3 b 4)
        1                               '(a b 1 c 2 3 b 4)
        1                               '(b 1 c 2 3 b 4)
        1                               '(1 c 2 3 b 4)
        2                               '(c 2 3 b 4)

<TODO: Fill in the remaining rows.>
|#

#|
b. Using the ideas you gained in those steps, implement `tally-numbers`
using a recursive helper.  You'll need to fill in the undefined
parts of the procedure below.
|#

(define tally-numbers
  (lambda (lst)
    (letrec ([helper
               (lambda (tally-so-far remaining)
                 undefined)])
      (helper undefined undefined))))

#|
c. Check your answers on some of the following lists

> (tally-numbers null)
> (tally-numbers (list 1 2 3))
> (tally-numbers (list "a" "b" "c"))
> (tally-numbers (list 1 "a" 2 "b" 3 "c"))

<TODO: Enter the results>
|#

#|
d. Update theh elper for `tally-numbers` to print out calls, and
call it on the list `'(5 a b 1 c 2 3 b 4)` to see if it matches your
answer to part a.

<TODO: Fill in the results of your call.>
|#

; +-------------------------------+----------------------------------
; | Exercise 4: Selecting numbers |
; +-------------------------------+

#|
a. You may recall that in the distant past, we wrote a procedure,
`select-numbers`, that, given a list of values, returns a list with
just the numbers from the original list.

Here's an attempt to implement that procedure using helper recursion.

;;; (select-numbers values) -> listof number?
;;;   values : list?
;;; Selects all the numbers in values
(define select-numbers
  (lambda (values)
    (letrec ([helper 
              (lambda (nums-so-far remaining)
                ; (displayln (list 'helper nums-so-far remaining))
                (cond
                 [(null? remaining)
                  nums-so-far]
                 [(not (number? (car remaining)))
                  (helper nums-so-far 
                          (cdr remaining))]
                 [else
                  (helper (cons (car remaining) nums-so-far)
                          (cdr remaining))]))])
      (helper null values))))

Add the code and documentation to your definitions pane.
|#

#|
b. As you may have observed in a previous problem, it can be 
helpful to understand tail recursive procedures by creating
a table whose columns are labeled with the parameters and which
each row gives the values of those parameters in one call.

Here's what we might expect those columns to have after we've done
the first few steps of the helper on the list `'(a b 1 c 2 3 b 4)`

        num-so-far                      remaining
        ----------                      ---------
        '()                             '(a b 1 c 2 3 b 4)
        '()                             '(b 1 c 2 3 b 4)
        '()                             '(1 c 2 3 b 4)
        '(1)                            '(c 2 3 b 4)

<TODO: Fill in the remaining five or so rows.>
|#

#|
c. Given that experiment, what output do you expect to get from 
`(select-numbers '(a b 1 c 2 3 b 4))`?

<TODO: Enter your answer here.>
|#

#|
d. Check your answer experimentally.

<TODO: Enter the expression and response from the interactions pane.>
|#

#|
e. If you did not get the answer you expected, uncomment the line that
logs procedure calls and run it again.  Then enter an explanation.
Note: We'll fix the issue in the next exercise.

<TODO: Enter "I got the expected answer" or an explanation>
|#

#| A |#

; +------------------------------------------+-----------------------
; | Exercise 5: Selecting numbers, revisited |
; +------------------------------------------+

#|
As you may have noted, the prior implementation of `select-numbers`
produces the list of values in reverse order that they appear in the
original list.  Rewrite the procedure so that it produces the list of
values in the same order as they appear in the original list.  You
may not use `append` in that implementation.
|#

(define select-numbers/new
  (lambda (values)
    (letrec ([helper 
              (lambda (nums-so-far remaining)
                ; (displayln (list 'helper nums-so-far remaining))
                (cond
                 [(null? remaining)
                  nums-so-far]
                 [(not (number? (car remaining)))
                  (helper nums-so-far 
                          (cdr remaining))]
                 [else
                  (helper (cons (car remaining) nums-so-far)
                          (cdr remaining))]))])
      (helper null values))))

#| B |#

; +-----------------------------+------------------------------------
; | Exercise 6: Exploring costs |
; +-----------------------------+

#|
You may have noted that we have two versions of `furthest-from-zero`
above.  The first uses a recursive kernel.  The second, alled
`furthest-from-zero/alt`, uses direct recursion.

Believe it or not, but the direct recursive version is incredibly
expensive.

Or at least we claim it is.  Let's check that claim.
|#

#|
a. Explain, in your own words, how `furthest-from-zero/alt` works.
|#

#|
b. What output do you expect from the following procedure call?
(Detail both the answer and the log messages from `displayln`.)

    > (furthest-from-zero/alt (list 8 5 3 1 0))

Output: <TODO: Enter>

Log messages:
  <TODO: Enter>
|#

#|
c. Check your answer experimentally.

<TODO: Enter the expression and results from the interactions pane.>
|#

#|
d. What output do you expect from the following procedure call?
(Detail both the answer and the log messages from `displayln`.)

    > (furthest-from-zero/alt (list 0 1 3 5 8))

Output: <TODO: Enter>

Log messages:
  <TODO: Enter>
|#

#|
e. Check your answer experimentally.

<TODO: Enter the expression and results from the interactions pane.>
|#

#|
f. Explain, in your own words, why one of the two results looks so
much worse.

<TODO: Enter your explanation.>
|#

#|
g. How many calls to `furthest-from-zero/alt` do you expect to see
if we ask for the values of `(furthest-from-zero/alt (range 8))`?

<TODO: Enter your answer.>
|#

#|
h. Check your answer experimentally.

<TODO: Copy and paste from the interactions pane.>
|#

; +-----------------------+------------------------------------------
; | Depending on time ... |
; +-----------------------+

#| 
We hope that there's time to do the next two exercises.  If not,
you should still read over them to understand the basic points.
|#

#| B |#

; +--------------------------------+---------------------------------
; | Exercise 7: Improving the code |
; +--------------------------------+

#|
As you may have noted, a major problem with `furthest-from-zero/alt`
is that we may have *two* identical recursive calls each time,
rather than one.  That's dangerous.  Tail recursion is one solution.
But we can also continue to use direct recursion, as long as we're
a bit more careful about how we do things.
|#

#|
a. One solution is to do something you should be inclined to do
anyway: Use a `let` binding to name the expressions we repeat.

    (let ([candidate (furthest-from-zero/alt (cdr numbers))]
          [alternate (car numbers)])

Rewrite `furthest-from-zero/alt` to use these names in place of the
values they name.  Your new version will be `furthest-from-zero/let`.
|#

;;; An alternate version of furthest-from-zero
(define furthest-from-zero/let
  (lambda (numbers)
    (displayln (list 'furthest-from-zero/let numbers))
    (if (null? (cdr numbers))
        (car numbers)
        (if (>= (abs (car numbers)) 
                (abs (furthest-from-zero/let (cdr numbers))))
            (car numbers)
            (furthest-from-zero/let (cdr numbers))))))

#|
b. What effect do you expect this naming to have on the efficiency of
the procedure?

<TODO: Explain the expected effect.>
|#

#|
c. Check your answer experimentally.

<TODO: Enter the results of your experiments here.
|#

#|
d. Just in case you weren't sure, you should find that you 
have 8 recursive calls for a list of length 8, rather than
the much larger number we saw before.
|#

#| A |#

; +--------------------------------------+---------------------------
; | Exercise 8: An alternate improvement |
; +--------------------------------------+

#|
a. Another solution is to observe that `futher-from-zero` looks a
whole lot like the inner `if` expression.

Rewrite `furthest-from-zero/alt` to use `further-from-zero` in
lieu of the inner `if` expression.  Your new version will be 
`furthest-from-zero/ffz`.
|#

;;; An alternate version of furthest-from-zero
(define furthest-from-zero/ffz
  (lambda (numbers)
    (displayln (list 'furthest-from-zero/ffz numbers))
    (if (null? (cdr numbers))
        (car numbers)
        (if (>= (abs (car numbers)) 
                (abs (furthest-from-zero/ffz (cdr numbers))))
            (car numbers)
            (furthest-from-zero/ffz (cdr numbers))))))

#|
b. What effect do you expect this naming to have on the efficiency of
the procedure?

<TODO: Explain the expected effect.>
|#

#|
c. Check your answer experimentally.

<TODO: Enter the results of your experiments here.
|#

#|
d. Just in case you weren't sure, you should find that you 
have 8 recursive calls for a list of length 8, rather than
the much larger number we saw before.
|#

; +---------------------------+--------------------------------------
; | For those with extra time |
; +---------------------------+

#|
If you find that you have extra time, you might choose to take
on one or more of the following exercises.
|#

; +----------------------------------+-------------------------------
; | Extra 1: Tallying multiple types |
; +----------------------------------+

#|
Write a procedure, `tally-numbers-strings-and-symbols`, that takes
as input a mixed list and produces a list of tallys of the number
of numbers, strings, and values.

    > (tally-numbers-strings-and-symbols null)
    '(0 0 0)
    > (tally-numbers-strings-and-symbols '(a 1 2 b "c" 3))
    '(3 2 1)
    > (tally-numbers-strings-and-symbols '(a b "c" "3" "e"))
    '(0 2 3)

You will find it useful to base `tally-numbers-strings-and-symbols` on
the helper-recursive `tally-numbers` your wrote earlier in this lab.

This time, you may to add more parameters to the recursive helper.
|#

(define tally-numbers-strings-and-symbols
  (lambda (lst)
    undefined))

; +---------------------------------+--------------------------------
; | Extra 2: Checking preconditions |
; +---------------------------------+

#|
Rewrite the original `furthest-from-zero` so that the primary procedure
(that is, `furthest-from-zero`) checks all of its preconditions before
calling the helper.
|#

;;; (furthest-from-zero numbers) -> real?
;;;   numbers : listof real?
;;; Determine the element in numbers which is furthest from
;;; zero (that is, has the largest value)
(define furthest-from-zero/new
  (lambda (numbers)
    (letrec ([helper
              (lambda (furthest-so-far remaining)
                ; (displayln (list 'helper furthest-so-far remaining))
                (if (null? remaining)
                    furthest-so-far
                    (helper (further-from-zero furthest-so-far 
                                               (car remaining))
                            (cdr remaining))))])
      (helper (car numbers) (cdr numbers)))))

; +-----------------------------------------------+------------------
; | Extra 3: Too many ways to find extreme values |
; +-----------------------------------------------+

#|
We ask you to find the number furthest from zero because finding the
"most extreme" value in a list is a common task.
You've now approached the problem in four ways:

* Using direct recursion.
* Using helper/tail recursion.
* Using a `let` binding.
* Using a helper procedure (`further-from-zero`) to choose the 
  more extreme of the values.
|#

#|
a. Which of the four ways do you prefer.  Why?

<TODO: Enter an answer.>
|#

#|
b. Which of these is most like what you'd do with `reduce`?

<TODO: Enter an answer.>
|#

; +--------------------------------------------+---------------------
; | Extra 4: Converting to tail-recursive form |
; +--------------------------------------------+

#|
We will often decide to convert a direct recursive procedure to
a tail-recursive procedure.  Give a process for doing so (or
at least approximately doing so).

<TODO: Enter an answer.>
|#