Class 19 — Monday, November 2
Quiz 6 first. Then week 3’s cases, as a switch: list functions written by hand, in your cmsc-120-lst project.
Lists in Java was due today. A9 is due Tuesday, November 3.
Outline
- A
switchon a list — keyboards down - By hand — pairs, at the keyboard
- Before the break: save to GitHub
- A list built by hand — keyboards down
- Building lists — pairs again
- Carrying the sum — keyboards down
- Keep going
- Before you leave: save again
- Before Wednesday
1. A switch on a list
Keyboards stop.
Week 3’s total, and the reading’s, side by side:
Now length, with its Empty case left out:
void main() {
IO.println(length(Lst.of(6, 9)));
}
// how many units there are
int length(Lst<Integer> units) {
return switch (units) {
case Lst.Link(var u, var rest) -> 1 + length(rest);
};
}Does Java run it? If it does, what does it print?
Java refuses it before anything runs: the switch expression does not cover all possible input values. Lst.java says a list is one of two things, an Empty or a Link, so a switch on a list has a case for each and no default, and Java checks that both are there, as it did for week 8’s enums. Pyret’s cases without | empty ran until an empty list arrived.
With the case back in, length(Lst.of(6, 9)) is 2, by week 3’s substitution: 1 + length([list: 9]), then 1 + (1 + length([list: ])), then 1 + (1 + 0).
2. By hand
- The navigator (not typing) says the examples first. Then they say the steps the function takes.
- The driver types the above, and decides how each step becomes Java.
- If either of you is stuck, drop the roles for a minute and talk it over.
- Swap at every function.
In a new file ByHand.java, beside Units.java. Each function is a switch on the list with a case for each kind, and calls itself on rest: no Lst.filter, Lst.map or Lst.fold. A // line above it, and at least two Check.is lines in main, one on the empty list, Lst.of().
length
int length(Lst<Integer> units) — how many units there are. length(Lst.of(4, 10, 20)) is 3.
Done when two checks pass, one on the empty list.
largest
int largest(Lst<Integer> units) — the largest unit, and 0 for the empty list. The larger of two numbers is Math.max(a, b).
Done when checks pass with the largest first, with it last, and on the empty list.
countOutlined
If you are done, here are two more.
int countOutlined(Lst<Integer> units) — how many units are outlined: 10 and up. The Link case has a question in it.
Done when checks pass on [4, 10, 20], on [4, 7] and on the empty list.
anyOutlined
boolean anyOutlined(Lst<Integer> units) — whether some unit is outlined. What does the empty list give back?
Done when checks pass with an outlined unit last, with none, and on the empty list.
3. Before the break: save to GitHub
Everyone, before the break.
In IDEA: Git → Commit… (Ctrl+K). Tick your files, write a line saying what you did, then Commit and Push… and Push. Then open your repository on GitHub and check that the commit is there.
If the push is refused, leave it for the end of class: your work is on this machine either way. The same project at home, and what to do when a push is refused: Git and GitHub at home.
4. A list built by hand
Keyboards stop. Predict first.
Last Monday’s 67 green squares need a list of 67 greens. Nobody types that into Lst.of; a function builds it, one link at a time:
void main() {
IO.println(copies(3, "green"));
IO.println(copies(-1, "green"));
}
// n copies of x
Lst<String> copies(int n, String x) {
if (n == 0) {
return new Lst.Empty<>();
} else {
return new Lst.Link<>(x, copies(n - 1, x));
}
}The first line prints [list: green, green, green]. What does the second line do?
It never arrives. copies(-1, "green") calls copies(-2, "green"), which calls copies(-3, "green"), and n never reaches 0; Java stops it when the calls pile too high, with a StackOverflowError. A call on rest always arrives: rest is a shorter list, and the empty list is at the end of every list. n - 1 arrives at 0 only from above. Java checked that section 1’s switch had both cases; nothing checks that the calls stop.
5. Building lists
Pairs, the same way, in ByHand.java. A function that gives back a list builds it as copies does, with new Lst.Link<>(…, …) and new Lst.Empty<>(). Check.is takes two lists.
copy
Lst<Integer> copy(Lst<Integer> units) — the same list, built again one link at a time. copy(Lst.of(4, 10, 20)) is [list: 4, 10, 20].
Then two more lines in main, and say to each other why they differ:
Done when two checks pass, one on the empty list, and you can say what each printed line asks.
outlined
Lst<Integer> outlined(Lst<Integer> units) — the outlined units only, in order: Wednesday’s outlined, without Lst.filter. The Link case has a question in it: u goes in front of the rest’s answer, or the rest’s answer is the whole answer.
Done when checks pass on [4, 10, 20], on [4, 7] and on the empty list.
widths
If you are done, here are two more.
Lst<Integer> widths(Lst<Integer> units) — each unit’s width, six times the unit: Wednesday’s widths, without Lst.map.
Done when two checks pass, one on the empty list.
copies
Section 4’s copies, in your file, with its checks: copies(3, "green") and copies(0, "green"). A check on a list of texts: Check.is(copies(2, "green"), Lst.of("green", "green")).
Done when both pass.
Then open Lst.java and find filter. It is outlined with one line changed: where yours asks u >= 10, it asks keep.test(first), the question it was handed, Wednesday’s u -> u >= 10. Every function in the file is this switch.
6. Carrying the sum
Keyboards stop. Predict first.
Section 1’s total adds on the way back, 4 + (10 + (20 + 0)): every call waits for the rest’s answer. Here is total a second way, with the sum so far carried down as an argument:
// all the units added up
int total(Lst<Integer> units) {
return totalFrom(0, units);
}
// sum, the units added up so far, plus the units still to add
int totalFrom(int sum, Lst<Integer> units) {
return switch (units) {
case Lst.Empty() -> sum;
case Lst.Link(var u, var rest) -> totalFrom(sum + u, rest);
};
}What is totalFrom(100, Lst.of(4, 10, 20))?
134: sum is the total so far, and the Empty case hands it back. total starts it at 0, so total(Lst.of(4, 10, 20)) is four calls, each carrying the sum so far: totalFrom(0, [list: 4, 10, 20]), totalFrom(4, [list: 10, 20]), totalFrom(14, [list: 20]), totalFrom(34, [list: ]), which is 34. Nothing waits: at each step the two arguments are everything the computation knows.
7. Keep going
If you are done, here are more, in ByHand.java.
largest, carried
int largestFrom(int best, Lst<Integer> units) — the largest of best and the units still to look at, best being the largest seen so far. Then int largestCarried(Lst<Integer> units), which is largestFrom(0, units).
Done when section 2’s three checks on largest pass on largestCarried.
runningTotals
Lst<Integer> runningTotals(Lst<Integer> units) — each unit added to everything before it: [4, 10, 20] gives [4, 14, 34]. The rest’s answer cannot know what came before it, so carry the sum, as totalFrom does, in a helper that gives back a list.
Done when checks pass on [4, 10, 20] and on the empty list.
append
Lst<Integer> append(Lst<Integer> xs, Lst<Integer> ys) — xs, then ys. append(Lst.of(1, 2), Lst.of(3)) is [list: 1, 2, 3]. The switch is on xs. What is the answer when xs is empty?
Done when checks pass with xs empty, with ys empty, and with neither.
reverse
Lst<Integer> reverse(Lst<Integer> xs) — the list backwards. append can put a one-element list, Lst.of(u), after something.
Done when reverse(Lst.of(1, 2, 3)) is [list: 3, 2, 1] and the empty list gives the empty list.
row
Img row(int n) — n green squares of side 20, side by side: Wednesday’s section 7, with copies(n, "green") for its list of colors.
Done when Img.width(row(67)) is 1340 and the row shows.
8. Before you leave: save again
As before the break, in section 3: commit, push, and check that the commit is on GitHub.
9. Before Wednesday
A9 is due Tuesday, November 3.