Streams

Functional programming comes to Java.

Functional programming

Based on “pure” functions, no mutation.

Heavy use of higher-order functions, i.e. functions that take functions as arguments and return functions as values

Purity allows laziness. (Or laziness requires purity.)

Pure functions

Return the same value whenever they are called with the same arguments.

Have no side effects. I.e. they just compute and return a value.

Laziness

Lazy evaluation is a form of evaluation where computation is deferred until the result of the computation is actually needed.

The opposte of lazy evaluation is “strict” or “eager” evaluation and is what you’re used to.

Higher-order functions

Java doesn’t really have free-standing functions since everything is a method.

But since Java 8, it has picked up some features that make it easier to treat some methods as functions, making APIs based aroud higher-order functions more comfortable.

Event handling

Before we get to streams, let’s look at another place where we want to pass around functions: event handling.

GUI events

In GUIs, you need to define what happens when certain events (such as a button being pressed or the mouse being clicked) occur.

As some of you know, the mechanism is to add a listener, an instance of a class that implements a specific interface with a method or methods that get called when certain events happen.

Old-style event handling

Since 1.1 and before Java 8, events were handled using anonymous inner classes like this:

button.addActionListener(
  new ActionListener() {
    public void actionPerformed(ActionEvent e) {
      foo();
    }
  }
);

Five lines just to say we want to call the foo method when the button is pressed. 🤦

Even that’s shorthand for what’s really going on

public class MyActionListener implements ActionListener {
  public void actionPerformed(ActionEvent e) {
    foo();
  }
}
button.addActionListener(new MyActionListener());

Modern event handling

button.addActionListener(e -> foo())

Lambdas

e -> foo() is called a “lambda” and it’s a kind of anonymous function.

This gets compiled into the same thing as the anonymous inner class but the compiler fills in all the boilerplate for us: it knows what interface we need to implement and there’s only one method in it so we can treat the lambda as the implementation of that method.

Note

Java lambdas are not weak sauce compared to the equivalent thing in Javascript, Common Lisp, or Scheme.

Python lambdas are maybe even more impoverished because Python actually hates functional programming.

Functional interfaces

Any interface with a only one abstract method is a “functional interface” meaning it can be thought of as representing a single function.

We can only use lambdas in places that expect some functional interface.

More lambdas

s -> s.toUpperCase()

(a, b) -> a + b

() -> 10

Method and constructor references

s -> s.toUpperCase() String::toUpperCase
n -> Math.abs(n) Math::abs
arg -> frob(arg) this::frob
arg -> obj.frob(arg) obj::frob
arg -> new Foo(arg) Foo::new
n -> new int[n] int[]::new

Streams

Streams represent a sequence of values.

May be infinite.

Can be transformed in a variety of ways.

They are lazy; to get an actual non-Stream value we need to provide some “terminal” operation.

Filter, map, reduce

Three tastes that go great together.

Filter

Filtering a stream produces a new stream containing only those elements that satisfy some predicate.

students.filter(s -> s.isSenior())

Map

Mapping a stream produces a new stream containing an element computed from each element of the original stream.

students.map(s -> s.lastName())

Laziness

Filter and map are both lazy: they just set up some objects that squirrel away the functions and wait until values are actually needed.

Reduce

Reducing a stream “boils down” a stream to a single value.

students.count()

There is a general reduce method on streams but any “terminal” operaton, such as count here, is a kind of reduction.

Reduce forces evaluation

Obviously to get the count of elements in the stream we have to actually iterate through the stream and count the elements.

Combining filter, map, and reduce

students
  .filter(s -> s.gpa() == 4.0)
  .map(s -> s.getName())
  .toList();

Where do streams come from?

Some important packages

Count starts with vowel

Procedural version.

public int countStartsWithVowel(String[] ss) {
  int count = 0;
  for (String s : ss) {
    if (isVowel(s.substring(0, 1))) count++;
  }
  return count;
}

Stream version

public int countStartsWithVowel(String[] ss) {
  return (int) Arrays
    .stream(ss)
    .map(s -> s.substring(0, 1))
    .filter(this::isVowel)
    .count();
}

Streams of primitive types

  • IntStream

  • DoubleStream

  • LongStream

map on reference vs primitve streams

On Stream<T> map takes a function from T to a potentially new type R, and returns a Stream<R>.

On primitive streams map takes an unary operator of the appropriate type (e.g. IntUnaryOperator) and returns another primitive stream of the same type.

Converting between stream types

  • mapToInt

  • mapToDouble

  • mapToLong

  • mapToObj (only on primitive streams)

Examples

// Stream<String> to Stream<Integer>
Stream.of("10", "20").map(Integer::parseInt)

// Stream<String> to IntStream
Stream.of("10", "20").mapToInt(Integer::parseInt)

// IntStream to Stream<Integer>
IntStream.of(10, 20).mapToObj(n -> n)

// IntStream to Stream<String>
IntStream.of(10, 20).mapToObj(String::valueOf)

// IntStream to DoubleStream
IntStream.of(10, 20).mapToDouble(n -> n)

Collectors

Helper class for making objects that can be passed to the general purpose collect terminal operation.

collect peforrms a “mutable reduction” where each element is collected by mutating some object.

This can be way more efficient than a purely functional style.

But it’s nicely hidden.

Collector examples

Adapted from Javadocs

Make a list

List<String> names = people
  .stream()
  .map(Person::getName)
  .collect(Collectors.toList());

Make any collection

In this case a TreeSet.

Set<String> set = people
  .stream()
  .map(Person::getName)
  .collect(Collectors.toCollection(TreeSet::new));

Join into a single string

String list = things
  .stream()
  .map(Object::toString)
  .collect(Collectors.joining(", "));

Total the value of some function

int total = employees.stream()
  .collect(Collectors.summingInt(Employee::getSalary));

Make a map to many values

Map<Department, List<Employee>> byDept = employees.stream()
  .collect(Collectors.groupingBy(Employee::getDepartment));

Make a map to a collected value

Map<Department, Integer> totalByDept = employees
  .collect(Collectors.groupingBy(
    Employee::getDepartment,
    Collectors.summingInt(Employee::getSalary))
  );

Partition the elements of a stream.

Map<Boolean, List<Student>> passingFailing = students
  .collect(
    Collectors.partitioningBy(
      s -> s.getGrade() >= PASS_THRESHOLD
    )
  );

Example

Hailstone sequences

Hailstone sequences comes from a math problem called the Collatz Problem. A hailstone sequence starts at at some positive integer, n, and then subsequent elements in the sequence are generated as n / 2 if n is even and 3 * n + 1 if n is odd.

The Collatz Problem, which has not been solved, asks, do all such sequences, starting from any positive n converge to 1?

Hailstone length

One question we can ask about hailstone sequences is how many steps does it take to converge to 1. Here’s how we might answer that question procedurally.

public long hailstoneLength(int start) {
  long count = 1;
  long n = start;
  while (n != 1L) {
    count++;
    n = n % 2 == 0 ? n / 2 : 3 * n + 1;
  }
  return count;
}

Aside: why long?

Note, we need to use long instead of int because for some numbers (such as 113,383) the sequence overflows 32-bits on the way to 1.

Note that there’s no guarantee that the hailstone sequence values always fits in 64 bits but it gives us more room. In fact we can check all the positive int values without overflow if we do the computations with longs.

Stream version

But a hailstone sequence is an infinite sequence so it is well-modeled by a stream. Here’s how we can build an IntStream of the hailstone sequence with a given starting point:

private long nextHailstone(long n) {
  return n % 2 == 0 ? n / 2 : 3 * n + 1;
}

public LongStream hs(int start) {
  return LongStream.iterate(start, this::nextHailstone);
}

Hailstone length, stream version

Then we can use a stream to answer the length question.

public long hailstoneLength(int start) {
  return 1 + hs(start).takeWhile(n -> n != 1).count();
}

Hailstone elements

And we can also use the stream to collect an array of the elements up to and including the 1.

public long[] hailstone(int start) {
  return LongStream
    .concat(
      hs(start).takeWhile(n -> n != 1),
      LongStream.of(1)
    )
    .toArray();
}

Hailstone lengths

Or we can make a stream of the lengths of the hailstone sequences starting from each positive int.

public LongStream hailstoneLengths() {
  return IntStream
    .iterate(1, n -> n + 1)
    .mapToLong(this::hailstoneLength);
}

Hailstone stats

hs.hailstoneLengths()
  .limit(Integer.MAX_VALUE)
  .boxed()
  .collect(Collectors.summarizingLong(n -> n)));
LongSummaryStatistics{
  count=2147483647,
  sum=455685569303,
  min=1,
  average=212.195129,
  max=1009
}