Lists in Java

Pyret’s list as a Java type: empty, or a first element linked to the rest. Map, filter and fold, the arrow, and cases as a switch.

Week 3’s lists, in Java. Coles’ book has no chapter on this; this page is the reading.

A list

Lst<Integer> hours = Lst.of(6, 9, 4, 11);
Lst<String> words = Lst.of("ab", "cde");

Lst.of makes a list from its elements, in order: [list: 6, 9, 4, 11] in Pyret. The type says what the elements are, in angle brackets: Lst<Integer> for whole numbers, which Java spells with the long name Integer inside the brackets, and Lst<String> for texts. Lst.of(), with nothing in it, is the empty list.

IO.println(hours) prints [list: 6, 9, 4, 11], as Pyret does, and Lst.length(hours) is 4. A list never changes: filter and map below give back new lists, as Pyret’s did.

What a list is

Download Lst.java and keep it beside your own file, as you keep Check.java. Do not edit it. It says what Pyret’s List says: a list is one of two things.

  • Lst.Empty(), the empty list: Pyret’s empty.
  • Lst.Link(first, rest), a first element linked to the rest of the list, itself a list: Pyret’s link(first, rest).

Both are records, as week 8’s were. Lst.of(6, 9) is short for the same list built by hand, one link at a time:

Lst<Integer> two = new Lst.Link<>(6, new Lst.Link<>(9, new Lst.Empty<>()));

<> lets Java work out the element type from what is around it.

Map, filter and fold

Lst.java has week 3’s three functions, with the arguments in week 3’s order: the function first, then the list.

Pyret Java
filter(lam(h): h > 8 end, hours) Lst.filter(h -> h > 8, hours)
map(lam(h): h * 2 end, hours) Lst.map(h -> h * 2, hours)
fold(lam(total, h): total + h end, 0, hours) Lst.fold((total, h) -> total + h, 0, hours)

They give back [list: 9, 11], [list: 12, 18, 8, 22] and 30.

The arrow

h -> h > 8 is Java’s lam(h): h > 8 end: a function written in place, with no name. Its parameter is before the arrow and its value after it; there is no return, because the part after the arrow is an expression. With two parameters they go in parentheses, (total, h) -> total + h: fold’s function takes the value so far and the next element, in that order, as Pyret’s did.

An arrow inside a function may use the names that function owns:

// the words longer than n letters
Lst<String> longer(Lst<String> words, int n) {
    return Lst.filter(w -> w.length() > n, words);
}

Two lists, and ==

IO.println(Lst.of(1, 2) == Lst.of(1, 2));        // false
IO.println(Lst.of(1, 2).equals(Lst.of(1, 2)));   // true

Each Lst.of makes new links on the heap, so the two names hold two addresses and == says false. .equals asks, as on any record, whether the parts are equal: the same elements in the same order. Check.is takes two lists and asks .equals:

Check.is(Lst.filter(h -> h > 8, hours), Lst.of(9, 11));

Cases, as a switch

Pyret took a list apart with cases: one branch for empty, one for link, which names the first element and the rest. Java’s switch does the same, with a case for each kind of list:

// all the hours added up
int total(Lst<Integer> hours) {
    return switch (hours) {
        case Lst.Empty() -> 0;
        case Lst.Link(var h, var rest) -> h + total(rest);
    };
}
fun total(hours :: List<Number>) -> Number:
  cases (List) hours:
    | empty => 0
    | link(h, rest) => h + total(rest)
  end
end

case Lst.Link(var h, var rest) names the parts of the link, as link(h, rest) did: var lets Java work out their types. There is no default: a list is an Empty or a Link and nothing else, so Java can check that both cases are there, as it did for week 8’s enums. total calls itself on rest, the smaller list, and the empty case is where it stops. Monday’s class writes functions this way.

What is inside Lst.java

Every function in it is that switch: filter, map and fold are week 3’s, written the way week 3 wrote them by hand, in Java. Open it and read length first.