Lab 6: Recurring, Again and Again

Hints & Guidelines

This week, we’ll be practicing solving problems that require list recursion. For some solutions, you’ll be allowed to use list library functions. For others, you’ll need to write recursive functions (using cases) as discussed in class.

Remember to follow the Design Recipe steps:

Design Recipe

Write the name, inputs (with types) and output type for your program.
Write some examples of what your program should do. Cover the various cases of the input, including the empty case for lists. For a list problem, writing 2-3 examples that handle a list and its suffixes can be helpful in seeing the pattern that defines the link case.
Write a task plan – a list of the computations you’ll need to build up your program. Annotate each item with a built-in operation or helper function you could write to handle that task.
For each recursive function you need to write, if the function operates over lists, copy the template code, replacing the function name, inputs, and types with ones that are relevant to your program.
```
fun my-fun(lst :: ?) -> ?
  cases (List) lst:
    | empty => 
    | link(fst, rst) => my-fun(rst)
  end
end
```
Note: fst and rst can be named anything – they are just names that we give the first and rest of the List lst.
Fill in the template with the code that is specific to the function you are trying to write.

Setup

Paste the following code into the definitions window (posns will come up in a later problem):

include image
import lists as L

data Posn:
  | posn(x :: Number, y :: Number)
end

Part 1: List Operations & Recursion

Use L.map to write the following functions:
- double-words(word-list :: List<String>) -> List<String>, which takes in a list of strings and doubles each element. For example, doubles-words([list: "hello", "friend"]) should return [list: "hellohello", "friendfriend"]
- create-stars(star-colors :: List<String>) -> List<Image> that takes in a list of strings representing valid colors and produces a list of stars (take a look at the Pyret image documentation if you can’t remember how to make a star). Each star should have a side length of 10.
Rewrite the functions from above, but this time without using L.map. Instead, use the template described in Hints & Guidelines. The function headings should be:
- double-words-no-map(word-list :: List<String>) -> List<String>
- create-stars-no-map(star-colors :: List<String>) -> List<Image>

Part 2: Yet More Recursion

Write a function generate-pattern(posn-list :: List<Posn>, img :: Image) -> Image that takes in:
- A list of Posns representing coordinates
- A background image
The function should output a new image composed of circles placed on the background at each coordinate. Each circle should be colored “blue” and have a radius of size 10.

For example, generate-pattern([list: posn(0,0), posn(100, 30), posn(190, 190)], square(200, "solid", "salmon")) should produce an image that looks like the following:

Note: Use place-image from the Pyret image documentation to put a circle onto an image at a specific coordinate (the “Scene” output type is just an image).
HINT: A brief review of Posns:
Posns take the form posn(x,y) where x represents the x-component and y represents the y-component. To make one, just replace x and y with the numbers you want. For example, if you write the following code in the definitions window:
```
posn1 = posn(5,6)
posn2 = posn(7,8)
```
You can do the following in the interactions window:
```
>>> posn1.x
5
>>> posn2.y
8
```
Note that both the x- and y- components of a posn are actually of type Number, so you can treat them like numbers. For example, you could define a new Posn in the definitions window like this:
```
posn3 = posn(posn1.x + 5, posn.y + 10)
```
And wind up with the following in the interactions window:
```
>>> posn3.x
10
>>> posn3.y
16
```
Write a function make-circles(rad-list :: List<Number>) -> Image that takes in a list of numbers representing radii and produces an image consisting of adjacent green circles. Each circle should have the radius of its corresponding list index. In other words, the first circle should have the same radius as the first element of rad-list, and so on.
The final circle in the image should always be a black circle of radius 10, which is not represented in the list.

For example, make-circles([list: 40,60,10]) should produce an image that looks like the following:

NOTE: For this problem, use explicit recursion rather than built-in list operators.
Now, we want a function that lets us change the colors of the circles as well. Write a function make-better-circles(rad-list :: List<Number>, color-list :: List<String>) -> Image that takes in:
- A list of Numbers representing radii
- A list of Strings representing valid Pyret colors
As before, the function should output an image of adjacent circles. This time, each circle should have both the color and radius of its corresponding list index. The first circle should be the same color as the first element of color-list and the size of the first element of rad-list, and so on. The final circle in the image should still be a black circle of radius 10, not in either list.

For example, make-circles([list: 30,40,50], [list: "orange", "olive", "blue"]) should produce an image that looks like the following:

Hint: You can access the first element of a list by doing my-list.first and the rest of the list by doing my-list.rest.
This time, use a built-in function called L.map2 as a helper function. L.map2 is like L.map but works on two input lists. For example:
```
L.map2(lam(x, y): x + y end,
     [list: 3, 5, 6], 
     [list: 20, 40, 70]) 
```
produces [list: 23, 45, 76]. Note that the function now takes two inputs, one from each list. The two input lists must be the same length.
L.map2 in our case should return a list of circles, which can then go through recursively to create an image containing all of the circles in that list.
Write a function spell-check-alot(word-list :: List<String>) -> List<String> which takes in a list of strings and replaces each instance of “alot” (1 list element) with “a” followed by “lot” (2 list elements)

HINT: If you’re having trouble approaching this problem, start by writing a function that replaces all instances of “alot” with “a lot” (both a single list element). Then, think about how to modify your function to create two list elements.

Part 3: Lists of lists

Lists can contain more complicated data than just numbers, string, or images. For example, lists can contain other lists! As an example, imagine that we need to store weather readings across several days. Each day would be captured as a list of temperature readings, as follows:

temp-data = 
  [list: 
    [list: 56, 58, 60, 64, 64, 58],
    [list: 62, 65, 65, 65, 65, 63, 60],
    [list: 45, 48, 50, 52, 53],
    [list: 53, 53, 51, 48, 45, 42]
  ]

Note that the inner lists can be of different lengths (the weather data is missing some readings).

We want to write a recursive function days-in-range that counts how many days had all of their temperatures within a given range. For example:

fun days-in-range(temps :: List, low :: Number, high :: Number) -> Number:
  ...
where:
  days-in-range(temp-data, 45, 60) is 1 # the last row
  days-in-range(temp-data, 65, 80) is 0 # no row has all temps above 65
end

Write a task list for days-in-range. For each task, state the name and input/output types of a function you will write to perform the task. After your list is done, contrast it to ours.
Write a function that takes one of the inner lists and the low/high range values and determines whether all of the temperatures are within that range (including the low/high values). Write an explicitly-named function (rather than a lam function) to check whether a temperature is between the low and high range values (having a named function sets up a later question).
Write a function that takes in a list like temp-data, as well as the low and high range values, and counts how many days have all temps within that range.

Understanding Recursion

Now, let’s step back and make sure you understand how this program evaluates. Here is a smaller data example:

temp-data-short = 
  [list: 
    [list: 56, 58, 60],
    [list: 45],
    [list: 53, 53]
  ]

Assume you were going to evaluate the expression

days-in-range(temp-data-short, 50, 60)

What is the sequence of function calls that get made as this program evaluates? Write out the list with just enough detail that you and your partner agree on what the inputs will be at each call.
Go to http://cpo.herokuapp.com/editor, which is the experimental Pyret version that shows you how programs evaluate. Copy and paste your data and code for just this temps problem into the editor. Press the Trace and Run button. At the prompt, run the day-in-range expression that you just explored by hand.

Press Trace Last. You should get a tree-shaped summary diagram of which function calls were made. If you don’t see a diagram with lots of calls, make sure the drop down on the upper left corner says “All” (the other two options let you expand the tree manually by clicking on the blue circles – each click will expand the tree; “depth first” lets you see the calls that get made in order). If you hover your mouse over a function call, the tool will show you the inputs to that call and the result of that call.

You read the diagram by following the calls in the leftmost branch until they end, then the next-leftmost branch, and so on (going “deep” when you can, else moving left to right). Did you predict the same sequence of calls?
As this program runs, your parameters (the temps, low range, and high range) take on many different values. Is this a potential source of error in your code? How might Pyret keep track of which values you have at each point in the diagram?
What questions do you have about recursion after working on this lab? Enter them in the following form, so we can go over them.

Another lab in the books!

Great work on conquering a recurrence assignment! It’s time to get back to your detective work.