teaching machines

CS 330 Lecture 24 – Lambdas

April 3, 2017 by . Filed under cs330, lectures, spring 2017.

Dear students,

There are at least four ways of defining functions in Haskell:

We discussed composition last time. We continue that today, but we also use it to jump into the fourth: lambdas.

Is Haskell the only language that supports composition? No. Does Java? It can. Remember our discussion of Perry’s stages of cognitive development. The advanced stages of cognitive development reject the idea that an authority has a monopoly on all that is good. Instead, the best kind of human takes good ideas from lots of sources and combines them into a maximally-informed way of operating.

So that we can be the best kind of human, let’s take this idea of composition to Java. We need to be able to write 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> {
  public Double evaluate(Double x) {
    return 9 / 5.0 * x;
  }
}

public static class Biaser implements Func1<Double, Double> {
  public Double evaluate(Double x) {
    return x + 32;
  }
}

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(), new Scaler());
  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. I’d like to introduce them in Haskell first, because they are a little simpler there.

Lambdas are expressions that yield a function, but which don’t give it a name. This lambda adds 1 to its parameter:

\x -> x + 1

This lambda reports if its parameter is the empty list or a list with one element:

\l -> null l || length l == 1

I could assign these lambdas to identifiers:

add1 = \x -> x + 1
few = \l -> null l || length l == 1

But that’s not usually what we do. If we wanted a named function, we would have used that syntax. Instead, lambdas love to be anonymous. They love to be used for a moment and thrown away. They are firecrackers. We light them and toss them into the hands of our friend functions, where they explode in glory.

Those functions that are willing to take on other functions as parameters are called higher-order functions. We’ve seen at least one of them: filter. Let’s write a function that filters out all the numbers in a particular range:

innies :: Ord a => a -> a -> [a] -> [a]
innies lo hi = filter (\x -> lo <= x && x <= hi)

Let’s use a lambda to write a function that gives us back a list of only the non-duplicated items in a list:

onlies :: Ord a => [a] -> [a]
onlies = concat . filter (\list -> length list == 1) . group . sort

While we’re here, let’s go ahead and implement our own filter function. As a warm-up, let’s write count, which is a higher-order function that accepts a predicate and a list. It runs this algorithm:

count = 0
for each element in list
  if predicate is true of element
    count += 1
return count

We implement this in Haskell like so:

count :: (a -> Bool) -> [a] -> [a]
count _ [] = 0
count predicate (first:rest)
  | predicate first = 1 + count predicate rest
  | otherwise = count predicate rest

We can use lambdas with count!

count (\(a, b) -> a < b) [(1, 2), (3, 3), (4, 5), (11, 10)]
count (\s -> length s < 5) ["I", "think", "it's", "impossible", "to", "really", "understand", "somebody", "what", "they", "want", "what", "they", "believe", "and", "not", "love", "them", "the", "way", "they", "love", "themselves"]

Lambdas are pretty great, but be careful. What’s wrong with these?

count (\x -> x > 0) [-3..3]
count (\c -> isUpper c) "You Get What You Need"
count (\x -> x % 2 == 0) [-4..4]

All three of these are cases of UFW—unnecessary function wrapping. We have existing functions that do the same thing, and there’s no need to define a new one:

count (> 0) [-3..3]
count isUpper "You Get What You Need"
count even [-4..4]

Let’s also write filter:

filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter predicate (first:rest)
  | predicate first = first + filter predicate rest
  | otherwise = filter predicate rest

Now, let’s jump back to Java. 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 ust 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 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? Let’s see an ActionListener in action:

public static void main(String[] args) {
  final JFrame frame = new JFrame("...");
  JButton button = new JButton("Quit");

  button.addActionListener(e -> frame.dispose());
  frame.add(button);

  frame.setSize(512, 512);
  frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 
  frame.setVisible(true);
}

That final in there takes some explaining. Someday we’ll discuss closures, which are lambdas with memory. But not today.

See you next time, when we discuss lambdas and higher-order functions!

Sincerely,