Lab 6: Recursion Again and Again

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

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

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: 

#|
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 ...

|#

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: 

fun sum-of-cubes(lst :: List<Number>) -> Number:
  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

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. 

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

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. 

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

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. 

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

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