====== Lab 6: Recursion Again and Again ======

~~NOTOC~~

15 October 2021

===== Learning Objectives =====

The purpose of this lab is to give you practice reading, understanding, and writing functions involving lists and recursion.

====== Setup =====
Create the file ''lab06.arr'' and copy/paste the following into it:
''import lists as L''

As usual, ask your instructor or a coach if you're stuck.
Remember to save your work every so often.

====== Exercise 1: Tracing =====


Look at the following recursive function. In class, you've seen this function or ones that are very similar (e.g., ''my-sum'').

<code>
fun my-product(lst :: List<Number>) -> Number:
  doc: ```returns the product of the numbers in list lst```
  cases (List) lst:
    | empty => 1
    | link(f, r) => f * my-product(r)
  end
where:
  my-product(empty) is ...
  my-product([list: 2, 3]) is ...
  my-product([list: 5, 2, 3]) is ...
end
</code>

Trace the execution of the ''my-product([list: 5, 2, 3])'', showing the values of ''lst'', ''f'', and ''r'' and the return value each time the function is called.
If ''lst'' is ''empty'', there are no values for ''f'' and ''r'', so you can leave those lines out. You should fill in the return values (in reverse order)
after you've shown the values of ''lst'', ''f'', and ''r'' for each call.

Write your solutions as comments in your file in this format:

<code>
#|
my-product([list: 5, 2, 3]):
lst is [list: 5, 2, 3]
f is ...
r is ...
return value is ...
it calls
my-product(...)
f is ...
r is ...
return value is ...
it calls

...

it calls
my-product(empty)
return value is ...

|#
</code>


====== Exercise 2: sum-of-cubes =====

Fill in the missing parts to write a function that takes in a list of Numbers and returns the sum of the cubes of the numbers:

<code>
fun sum-of-cubes(lst :: List<Number>) -> Number:
  doc: "computes the sum of the cubes of the numbers in lst"
  cases (List) lst:
    | empty      => ...
    | link(f, r) => ...
  end
where:
  sum-of-cubes(empty) is 0
  sum-of-cubes([list: 1, 2, 3]) is 36
end
</code>

====== Exercise 3: list-to-string =====

Fill in the missing parts to write a function that takes in a list of Strings and returns a single string with all the strings "glued" together.
For example ''%%list-to-string([list: "ab", "cd"])%%'' should return the string ''%%"abcd"%%''. Your function should call ''string-append'' to glue two strings together.
<code>
fun list-to-string(lst :: List<String>) -> String:
  doc: ```returns a single string
       consisting of all of the strings in list
       lst 'glued' together```

  ...

where:
  list-to-string(empty) is ""
  list-to-string([list: "hello"]) is "hello"
  list-to-string([list: "hello ", "world"]) is "hello world"
  list-to-string([list: "one", "two", "three"]) is "onetwothree"
end
</code>

====== Exercise 4: max-pos-num =====

Fill in the missing parts to write a function ''max-pos-num'' that takes in a list of positive numbers and 
returns the largest number on the list. If the list is empty, ''max-pos-num'' should return -1. Note that
every positive number is greater than -1. Your function should call ''num-max'' to find the maximum of two
numbers.

<code>
fun max-pos-num(lst :: List<Number>) -> Number:
  doc: ```returns the maximum 
       element of a list of positive numbers; 
       if the list is empty, returns -1.
       Assume that the input list does not have 
       any negative numbers```
  ...

    
    
where: 
  max-pos-num(empty) is -1
  max-pos-num([list: 3, 5, 1, 4]) is 5
end
</code>

====== Exercise 5: long-strings =====

Fill in the missing parts to write a function ''long-strings'' that takes in a list of strings ''lst'' 
and a Number ''len'' and returns a list that includes all of the strings
from ''lst'' whose length is greater than ''len''. 

<code>
fun long-strings(lst :: List<String>, len :: Number) -> List<String>:
  doc: ```returns a list consisting
       of those elements of lst
       that are longer than len```
  cases (List) lst:
    | empty => ...
    | link(f, r) => 
      if string-length(f) > len:
        ...
      else:
        ...
      end
  end
where:
  long-strings(empty, 0) is empty
  long-strings([list: "the", "quick", "brown", "fox"], 4) is [list: "quick", "brown"]
  long-strings([list: "the", "quick", "brown", "fox"], 5) is empty
  long-strings([list: "the", "quick", "brown", "fox"], 2) is [list: "the", "quick", "brown", "fox"]
end
</code>

**Optional**:
After you have completed the code for ''long-strings'', 
show how to use ''L.filter'' to accomplish the same thing that ''long-strings'' does (with much less code).

===== Submitting the Lab =====

  * When you've complete the exercises, show your code to me or one of our coaches. \\ \\
  * Upload your ''lab06.arr'' file to the Lab 6 assignment on Gradescope.