teaching machines

CS 330: Lecture 31 – HOFs and Lambdas in Java

Dear students,

Is Haskell the only language that supports composition and higher-order functions? No. Does Java? It can be made to! Let’s do that today. We start by porting the . operator.

What do you suppose the type signature of . is in Haskell? Well, it takes in two functions and gives back a new one that bridges from the second through the first:

(.) :: (b -> c) -> (a -> b) -> (a -> c)

So, in Java, we will need to create a new type that models a function of arity 1, takes in a parameter of one type, and gives back a return value of another:

interface Func1<T, U> {
  public U evaluate(T x);
}

We can make some implementers of this type:

public static class Scaler implements Func1<Double, Double> {
  private double factor;

  public Scaler(double factor) {
    this.factor = factor;
  }

  public Double evaluate(Double x) {
    return factor * x;
  }
}

public static class Biaser implements Func1<Double, Double> {
  private double bias;

  public Biaser(double bias) {
    this.bias = bias;
  }

  public Double evaluate(Double x) {
    return x + bias;
  }
}

Now, we’d really like to be able to write something like this:

public static void main(String[] args) {
  Func1<Double, Double> c2f = Composer.compose(new Biaser(32), new Scaler(1.8));
  System.out.println("c2f.evaluate(100): " + c2f.evaluate(100.0));
}

And we can, though it gets a bit ugly:

class Composer {
  public static <A, B, C> Func1<A, C> compose(Func1<B, C> f,
                                              Func1<A, B> g) {
    return new Func1<A, C>() {
      public C evaluate(A x) {
        return f.evaluate(g.evaluate(x));
      }
    };
  }
}

I hope we can agree that Haskell does this very nicely with the . operator. We can improve on Java’s solution, however. In Java 8, we got lambdas. We’ve already seen them in Haskell as expressions that yield a function, but which don’t give it a name.

The syntax for lambdas in Java is not all that different:

(param1, param2, ...) -> {statement1; statement2; ...}

If there’s only one formal parameter and only one statement, we can drop some punctuation:

param -> statement

We can define biaser and scaler using the lambda syntax:

Func1<Double, Double> biaser = x -> x + 32;
Func1<Double, Double> scaler = x -> 1.8 * x;
Func1<Double, Double> c2f = Composer.compose(biaser, scaler);

Note that we still need the Func1 interface. Java lambdas make it feel like you’ve divorced an action from an object (or a verb from a noun), but really Java lambdas are just syntactic sugar for the old way of creating anonymous implementations of an interface. That sugar is sweet enough for us to care, because Java’s a heavy language.

We can simplify Composer as well:

class Composer {
  public static <A, B, C> Func1<A, C> compose(Func1<B, C> f,
                                              Func1<A, B> g) {
    return x -> f.evaluate(g.evaluate(x));
  }
}

When can we use lambdas in Java? Whenever there’s an interface with a single abstract method (SAM). The structure of a lambda only allows us to provide the implementation of one block of code, so this should make sense. The Java specification defines SAMs as functional interfaces, and they even added an annotation that we can use to help the compiler make sure we’re following the definition:

@FunctionalInterface
interface Func1<T, U> {
  public U evaluate(T x);
}

If we add extra methods or remove the one we have, we’ll get a compilation error.

Can you think of any such interfaces? How about ActionListener? Or Comparable? Or Runnable?

Now let’s make the ideas real with a Program This:

Write the necessary Java 8 code to filter a List. Allow clients of your code to supply their own filtering criteria.

Here’s my solution.
To leave a hole in the filtering algorithm, we must leave a parameter for the predicate. We’ll use a functional interface so we can drop in a lambda:
@FunctionalInterface
interface Predicate<T> {
  boolean isKeeper(T x);
}

class Library {
  public static <T> List<T> filter(List<T> list, Predicate<T> predicate) {
    ArrayList<T> keepers = new ArrayList<T>();
    for (int i = 0; i < list.size(); ++i) {
      if (predicate.isKeeper(list.get(i))) {
        keepers.add(list.get(i));
      }
    }
    return keepers;
  }
}

Let’s test this out with our planets, as we did in Haskell:

class Planet {
  private String name;
  private double ausFromTheSun;
  private double relativeMass;

  public Planet(String name,
                double ausFromTheSun,
                double relativeMass) {
    this.name = name;
    this.ausFromTheSun = ausFromTheSun;
    this.relativeMass = relativeMass;
  }

  public String getName() {
    return name;
  }

  public double getAUs() {
    return ausFromTheSun;
  }

  public double getMass() {
    return relativeMass;
  }

  public String toString() {
    return String.format("%15s %6.2f %6.2f%n", name, ausFromTheSun, relativeMass);
  }
}

Now we can make a list:

public class Main {
  public static void main(String[] args) {
    List<Planet> planets = Arrays.asList(
      new Planet("Saturn", 9.5, 95.0),
      new Planet("Earth", 1.0, 1.0),
      new Planet("Venus", 0.7, 0.815),
      new Planet("Jupiter", 5.2, 318.0),
      new Planet("Uranus", 19.6, 14.0),
      new Planet("Neptune", 30.0, 17.0),
      new Planet("Mars", 1.5, 0.107),
      new Planet("Mercury", 0.4, 0.055)
    );
  }
}

With these in place, we can execute the same queries as we did in Haskell:

System.out.println(Library.filter(planets, p -> p.getMass() > 1));
System.out.println(Library.filter(planets, p -> p.getAUs() < 2.2));
System.out.println(Library.filter(planets, p -> p.getName().contains("u")));

Let’s do another Program This!

Write the necessary Java 8 code to map a function over a List. Make the code as general as possible, allowing its clients to supply their own transformation function.

Here’s my solution.
interface Transformer<T, U> {
  U transform(T x);
}

class Library {
  // ...

  public static <T, U> List<U> map(List<T> olds,
                                   Transformer<T, U> transformer) {
    ArrayList<U> news = new ArrayList<U>();
    for (int i = 0; i < olds.size(); ++i) {
      news.add(transformer.transform(olds.get(i)));
    }
    return news;
  }
}

It’s not as pretty as Haskell, but remember, we only have to write the overall algorithm once! Let’s see it used with some lambdas:

System.out.println(Library.map(planets, p -> p.getName()));
String[] names = {"Alice", "Bob", "Carol", "Diphthong"};
System.out.println(Library.map(Arrays.asList(names), name -> name + ", Lord of Catan"));
Integer[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
System.out.println(Library.map(Arrays.asList(nums), num -> 2 * num));

In Haskell, we learned that there are situations where lambdas simply wrap around another function, which makes them kind of pointless. If it’s really some other function we want to call, we should just pass that function off instead unnecessarily wrapping it up in another function. Can we do that in Java 8? Yes, sometimes. We can use method references:

System.out.println(Library.map(planets, Planet::getName));

Okay, let’s visit one last abstraction, the for-each pattern:

for each item in list
  do something with that item (call a method, print, etc.)

This pattern only makes sense in a language with side effects. As you can see, it doesn’t return anything. It just does stuff. We might implement it in Java like this:

interface Visitor<T> {
  void visit(T x);
}

class Library {
  // ...

  public <T> void foreach(List<T> list,
                          Visitor<T> visitor) {
    for (T item : list) {
      visitor.visit(item);
    }
  }
}

The algorithm is simpler here, so we don’t gain as much as we did with filter and map, but still, the fewer braces the better!

Library.foreach(planets, p -> System.out.print(p));
Library.foreach(planets, System.out::print);

For completeness sake, let’s abstract away the fold algorithm in Java. Let’s start by considering the type signature in Haskell:

fold :: (a -> b -> b) -> b -> [a] -> b
fold mix zero list = ...

The mixing function accepts an element from the list and mixes into our mix to produce a new mix. In Java, this is the equivalent functional interface:

@FunctionalInterface
public interface Mixer<T, U> {
  U mix(T item, U mix);
}

We can write fold in terms of this interface like so:

public class Library {
  public static <T, U> U fold(List<T> list,
                              Mixer<T, U> mixer,
                              U zero) {
    U mix = zero;
    for (T element : list) {
      mix = mixer.mix(element, mix); 
    }
    return mix;
  }
}

And now we fold over lists any time we want with just a little code:

Integer[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Integer sum = Library.fold(Arrays.asList(nums), (x, sum) -> x + sum, 0);

Here’s your TODO list:

  • Find a resource that describes Java’s new-ish Streams API. On a quarter sheet, write some interesting computation that chains together a gauntlet of processing using Streams.

See you next time, when we discuss the function to end all functions: fold/reduce/inject!

Sincerely,

P.S. It’s time for a haiku!

Mom, I want a dog
This one’s ears, that one’s muzzle…
Would you okay nine?

P.P.S. Here’s the code we wrote together:

Function1.java

@FunctionalInterface
public interface Function1<T, U> {
  public U evaluate(T value); 
  /* public void foo(); */
}

Library.java

import java.util.ArrayList;
import java.util.List;

public class Library {
  public static <A, B, C> Function1<A, C> compose(Function1<B, C> f,
                                                  Function1<A, B> g) {
    return new Function1<A, C>() {
      public C evaluate(A value) {
        return f.evaluate(g.evaluate(value));
      }
    };
  }

  public static <A> List<A> filter(Predicate<A> predicate,
                                   List<A> list) {
    ArrayList<A> keepers = new ArrayList<A>();

    for (A item : list) {
      if (predicate.isValid(item)) {
        keepers.add(item);
      }
    }

    return keepers;
  }

  public static <A, B> List<B> map(Transformer<A, B> xform,
                                   List<A> list) {
    ArrayList<B> keepers = new ArrayList<B>();

    for (A item : list) {
      keepers.add(xform.transform(item));
    }

    return keepers;
  }
}

Main.java

public class Main {
  public static void main(String[] args) {
    /* Scaler scaler = new Scaler(1.8); */
    /* Biaser biaser = new Biaser(32.0); */

    Function1<Double, Double> scaler = x -> 1.8 * x;
    Function1<Double, Double> biaser = x -> x + 32;
    Function1<Double, Double> c2f = Library.compose(biaser, scaler);

    Double celsius = 100.0;
    System.out.println("c2f.evaluate(celsius): " + c2f.evaluate(celsius));
    /* Double fahrenheit = biaser.evaluate(scaler.evaluate(celsius)); */
    /* System.out.println("fahrenheit: " + fahrenheit); */

    /* System.out.println("scaler.evaluate(100): " + scaler.evaluate(100.0)); */
  }
}

/* class Scaler implements Function1<Double, Double> { */
  /* private Double factor; */

  /* public Scaler(Double factor) { */
    /* this.factor = factor; */
  /* } */

  /* public Double evaluate(Double x) { */
    /* return x * factor; */
  /* } */
/* } */

/* class Biaser implements Function1<Double, Double> { */
  /* private Double bias; */

  /* public Biaser(Double bias) { */
    /* this.bias = bias; */
  /* } */

  /* public Double evaluate(Double x) { */
    /* return x + bias; */
  /* } */
/* } */

Planet.java

public class Planet {
  private String name;
  private double ausFromTheSun;
  private double relativeMass;

  public Planet(String name,
                double ausFromTheSun,
                double relativeMass) {
    this.name = name;
    this.ausFromTheSun = ausFromTheSun;
    this.relativeMass = relativeMass;
  }

  public String getName() {
    return name;
  }

  public double getAUs() {
    return ausFromTheSun;
  }

  public double getMass() {
    return relativeMass;
  }

  public String toString() {
    return String.format("%15s %6.2f %6.2f%n", name, ausFromTheSun, relativeMass);
  }
}

Predicate.java

@FunctionalInterface
public interface Predicate<A> {
  public boolean isValid(A item); 
}

FilterTest.java

import java.util.Arrays;
import java.util.List;

public class FilterTest {
  public static void main(String[] args) {
    List<Planet> planets = Arrays.asList(
       new Planet("Saturn", 9.5, 95.0),
       new Planet("Earth", 1.0, 1.0),
       new Planet("Venus", 0.7, 0.815),
       new Planet("Jupiter", 5.2, 318.0),
       new Planet("Uranus", 19.6, 14.0),
       new Planet("Neptune", 30.0, 17.0),
       new Planet("Mars", 1.5, 0.107),
       new Planet("Mercury", 0.4, 0.055)
      ); 

    /* List<Planet> keepers = Library.filter(planet -> planet.getName().equals("Saturn"), planets); */
    /* System.out.println("keepers: " + keepers); */

    List<Planet> keepers = Library.filter(planet -> planet.getName().contains("t"), planets);
    System.out.println("keepers: " + keepers);

    List<String> newPlanets = Library.map(planet -> "New " + planet.getName(), planets);
    System.out.println("newPlanets: " + newPlanets);
  }
}

Transformer.java

@FunctionalInterface
public interface Transformer<A, B> {
  B transform(A item); 
}

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *