Class 22 — Wednesday, November 11

for: the three lines about the counter in one header; a loop inside a loop, and the pictures it draws; map, filter and fold opened, as loops with an arrow as a parameter.

A10 first, on the projector. Then for.

A10 was due last night. A11 goes out today and is due Tuesday, November 17. Progress Exam 3 is on Monday, in the first half of class; the readings for Monday are [CU] 6.2 — for Loops and [CU] 6.4 — Nested Loops.

Outline

  1. The three lines, in one header — keyboards down
  2. Counting loops — pairs, at the keyboard
  3. Before the break: save to GitHub
  4. A loop inside a loop — predict, then run
  5. Boards — pairs again
  6. map, opened — keyboards down
  7. Your own map, filter and fold — pairs
  8. Before you leave: save again
  9. Before Monday

1. The three lines, in one header

Keyboards stop.

Monday’s close asked for the three lines of sumTo that are about i: where it starts, the question that stops the loop, and the line that moves it on. A for loop puts the three in its header, in that order, and the body keeps what is left:

// 1 + 2 + ... + n, Monday's
int sumTo(int n) {
    int sum = 0;
    int i = 1;
    while (i <= n) {
        sum = sum + i;
        i = i + 1;
    }
    return sum;
}
// 1 + 2 + ... + n, as a for
int sumTo(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum = sum + i;
    }
    return sum;
}

What matches what. int i = 1; before the while is the header’s first part, run once. i <= n is its second, asked before every round. i = i + 1, the body’s last line, is its third, run after the body every round, and spelled i++ there, which is where the reading’s shorthand lives from now on. The rule, in Monday’s notation:

for (S1; E; S2)        S1;
    BLOCK           ->  while (E) {
                            BLOCK
                            S2;
                        }

Now predict:

int sum = 0;
for (int i = 0; i < 3; i++) {
    sum = sum + i;
}
IO.println(sum);

3, or 6?

3: i is 0, 1, 2, and the round where i would be 3 never runs, since 3 < 3 is false. Counting from 0 with < is how Java counts most things, positions in a list included; counting from 1 with <= is how people count. Both are fine, and the two mixed, 0 with <=, gives one round too many.

2. Counting loops

Pairs protocol
  1. The navigator (not typing) says the examples first. Then they say the steps the function takes.
  2. The driver types the above, and decides how each step becomes Java.
  3. If either of you is stuck, drop the roles for a minute and talk it over.
  4. Swap at every function.

In a new file Fors.java, beside Walks.java. Each function is a for loop, no while, no call to itself and no Lst function but Lst.of. A // line above it, and at least two Check.is lines in main, one at the edge: 0, or the empty list.

sumTo

Section 1’s, with Monday’s checks: sumTo(100) is 5050, sumTo(0) is 0.

Done when both pass.

factorial

int factorial(int n) — 1 * 2 * ... * n, and 1 for 0: factorial(5) is 120.

Done when checks pass on 5, on 0 and on 10, which is 3628800.

copies

Lst<String> copies(int n, String x) — Monday’s, n copies of x, as a for: copies(3, "green") is [list: green, green, green].

Done when two checks pass, one on 0.

sumOfSquares

If you are done, here are two more.

int sumOfSquares(int n) — 1*1 + 2*2 + ... + n*n: sumOfSquares(3) is 14.

Done when two checks pass, one on 0.

powersOfTwo

Lst<Integer> powersOfTwo(int n) — the first n powers of two, from 1, in order: powersOfTwo(4) is [list: 1, 2, 4, 8]. A list built at the front comes out backwards, so either turn it round at the end, as Monday, or count down and build the last element first.

Done when checks pass on 4, on 1 and on 0.

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 loop inside a loop

Write your prediction in the Journal before anyone runs anything.

int count = 0;
for (int r = 1; r <= 3; r++) {
    for (int c = 1; c <= 4; c++) {
        count = count + 1;
    }
}
IO.println(count);

What does it print, and how did you count?

12. The inner loop runs all its rounds, four of them, for every single round of the outer one, and there are three of those: 3 * 4, not 3 + 4. The outer loop’s body is the whole inner loop.

A loop inside a loop is how a picture gets rows. board(3, 4, 10) is three rows of four outline squares, 40 wide and 30 high; the inner loop puts the squares of one row side by side, the outer loop puts the rows one above the other:

// rows by cols outline squares of side unit, one picture
Img board(int rows, int cols, int unit) {
    Img made = Img.rectangle(0, 0, "solid", "white");
    for (int r = 0; r < rows; r++) {
        Img row = Img.rectangle(0, 0, "solid", "white");
        for (int c = 0; c < cols; c++) {
            row = Img.beside(row, Img.square(unit, "outline", "black"));
        }
        made = Img.above(made, row);
    }
    return made;
}

Img.rectangle(0, 0, "solid", "white") is a picture of nothing, as in week 9: the starting value for a picture built with beside or above.

5. Boards

Pairs, the same way, in Fors.java. A check on a picture is on its Img.width and Img.height, never on the picture.

row

Img row(int n, int unit) — n black outline squares of side unit, side by side: row(4, 10) is 40 wide and 10 high.

Done when checks on the width and the height pass, and row(0, 10) is 0 wide.

board

Section 4’s, written with row: one loop, with row(cols, unit) where the inner loop was. board(3, 4, 10) is 40 by 30.

Done when both sizes check.

checkerboard

Img checkerboard(int n, int unit) — n by n solid squares, black and red by turns, as a checkerboard: the square in row r and column c is black when r + c is even. A ? : on (r + c) % 2 picks the color.

Done when checkerboard(8, 5) is 40 by 40, and it looks like one when you show it.

staircase

If you are done, here are two more.

Img staircase(int n, int unit) — n rows, the first of one square and each one square longer, left to right. The inner bound depends on the outer counter.

Done when staircase(3, 10) is 30 by 30 and staircase(0, 10) is 0 wide.

timesRow

Lst<Integer> timesRow(int i, int n) — i times 1, 2, ..., n, in order: timesRow(3, 4) is [list: 3, 6, 9, 12].

Done when checks pass on that and on timesRow(2, 0).

6. map, opened

Keyboards stop.

Week 10’s Lst.map(u -> u * 2, Lst.of(1, 2, 3)) is [list: 2, 4, 6]. The arrow is a function handed to map as a value, and Lst.java has carried map since then as a switch that calls itself. Here is the same walk as a loop, with the arrow as a parameter:

// f of each element, in order: Lst.map, as a loop
Lst<Integer> mapped(Function<Integer, Integer> f, Lst<Integer> xs) {
    Lst<Integer> made = new Lst.Empty<>();
    for (Lst<Integer> todo = xs; todo instanceof Lst.Link(var u, var rest); todo = rest) {
        made = new Lst.Link<>(f.apply(u), made);
    }
    return backwards(made);
}

Two things are new. Function<Integer, Integer> f is a parameter whose value is a function, from a number to a number, and f.apply(u) calls it. And the for header holds Monday’s walk: todo starts at the list, the question is the pattern, and todo = rest moves it on.

What is f in mapped(u -> u * 2, Lst.of(1, 2, 3)), and what is f.apply(2)?

7. Your own map, filter and fold

Pairs, the same way, in Fors.java. Monday’s backwards, as a for, goes in the file too.

doubled

Lst<Integer> doubled(Lst<Integer> xs) — each element doubled, in order, as a loop: doubled(Lst.of(1, 2, 3)) is [list: 2, 4, 6].

Done when two checks pass, one on the empty list.

myMap

Section 6’s mapped, under this name, with checks that hand it two different arrows, u -> u * 2 and u -> u * u.

Done when both pass, and the empty list gives the empty list.

myFilter

Lst<Integer> myFilter(Predicate<Integer> keep, Lst<Integer> xs) — the elements keep says yes to, in order: Lst.filter as a loop. A Predicate<Integer> is a function from a number to a boolean, and keep.test(u) asks it.

Done when checks pass with u -> u >= 10 and with u -> u < 10 on [4, 10, 20], and on the empty list.

myFold

If you are done, here are two more.

int myFold(BiFunction<Integer, Integer, Integer> combine, int base, Lst<Integer> xs) — Lst.fold as a loop, over a list of numbers: the value so far starts at base, and each round it becomes combine.apply(soFar, u).

Done when myFold((s, u) -> s + u, 0, Lst.of(4, 10, 20)) is 34, myFold((s, d) -> s * 10 + d, 0, Lst.of(1, 2, 3)) is 123, and the empty list gives base.

myLength

int myLength(Lst<Integer> xs) — how many elements, as a for over the list.

Done when two checks pass, one on the empty list.

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 Monday

Progress Exam 3 is Monday, in the first half of class; its page says what it covers and how to prepare. A11 is due Tuesday, November 17. The readings, [CU] 6.2 — for Loops and [CU] 6.4 — Nested Loops, are due before Monday.