Functions, closures, and objects: implementing a filter function in Scheme and Java

24 Dec 2007

Continuing with the theme of functions and closures (Registering JavaScript object methods as callbacks, Python bound methods), I thought I’d have a look at the relationship between functions, closures, and objects. I’ll build a filter, that returns elements from a collection for which a given predicate is true, in Scheme (a language with first-class functions and closures, but no objects), and in Java (a language with objects, but no first-class functions or closures.)

A function is an object with an "apply" method

In Scheme we can define a filter function that takes two parameters: a function (the predicate), and a list. It will call the predicate function on each element in the list, returning a new list containing all of the elements for which the predicate is true:

(define (filter pred lis)
  ; if lis is empty
  (if (null? lis)
    ; return an empty list
    '()
    ; otherwise, if the predicate is true on the first element
    (if (pred (car lis))
      ; return the first element concatenated with the
      ; result of calling filter on the rest of lis
      (cons (car lis) (filter pred (cdr lis)))
      ; otherwise (if the predicate was false) just
      ; return the result of filtering the rest of lis
      (filter pred (cdr lis)))))

We can then define a predicate and use it to filter:

(define (non-negative n)
  (>= n 0))

(filter non-negative '(-2 3 7 1)) ; (3 7 1)
(filter non-negative '(100 -9 8)) ; (100 8)

In Java, we don’t have first-class functions, but we do have objects. And we can define a Predicate as an object with a public method that takes a single parameter and returns a boolean:

public interface Predicate<T> {
    public boolean apply(T arg);
}

We can now write our Java filter function as a method that takes two parameters: a Predicate and a Collection:

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

public class Utils {
    public static <T> List<T> filter(Predicate<T> pred, Collection<T> c) {
        List<T> filtered = new ArrayList<T>();
        // loop through all the elements in c
        for (T obj : c) {
            // if the predicate is true for the current element
            if (pred.apply(obj)) {
                // append it to the result list
                filtered.add(obj);
            }
        }
        return filtered;
    }
}

NonNegative.java:

public class NonNegative implements Predicate<Integer> {
    public boolean apply(Integer n) {
        return n >= 0;
    }
}

With Predicate, Utils.filter, and NonNegative defined we can now filter:

// as our NonNegative class instances have no state,
// we only need one
Predicate<Integer> pred = new NonNegative();
Utils.filter(pred, Arrays.asList(-2, 3, 7, 1));
Utils.filter(pred, Arrays.asList(100, -9, 8));

The Scheme and Java examples above operated on collections of numbers but the filter functions (and Predicate interface in the Java case) are generic – they can filter collections of any type and filter on any provided predicate logic.

A closure is an object with an "apply" method and some state

Let’s say we want to filter all numbers greater than 4. We could define a greater-than-4 function:

(define (greater-than-4 n)
  (> n 4))

And if we wanted to filter all numbers greater than 1, we could define a function for that too. The greater-than-1 function is going to be very similar to greater-than-4 and it would be quite convenient to write a generic greater-than function:

(define (greater-than m n)
  (> n m))

(greater-than 4 1) ; false
(greater-than 4 20) ; true

Now, if we want to use our greater-than predicate with our filter function, we have a problem: the filter function expects the predicate to be a function that takes exactly one parameter (the element currently being considered), not two.

We can make our greater-than predicate work with our filter function by currying it:

(define (greater-than m)
  ; return a closure:
  ; a function that takes one parameter
  ; with a binding to the value provided for m
  (lambda (n)
    (> n m)))

We have rewritten greater-than to be a builder of functions (that take one parameter, as we need for filter). Rather than calculating if n is greater than m immediately, we delay the test and package it up into a closure and return that. We provide the parameters m and n in two stages: m is provided when we call greater-than (and stored for later use in the closure) and n is provided whenever the function returned from greater-than is called. For example, if we wanted to calculate 1 > 4 and 20 > 4:

(define greater-than-4 (greater-than 4))
(greater-than-4 1) ; false
(greater-than-4 20) ; true
; or, without naming the function
((greater-than 4) 1) ; false
((greater-than 4) 20) ; true

It is this two-stage quality that enables us to use greater-than with our filter function:

(filter (greater-than 4) '(-2 3 7 1)) ; (7)
(filter (greater-than 10) '(100 -9 8)) ; (100)

We can do something very similar in Java, but rather than a closure we use an object. We can implement GreaterThan as a Predicate in which m is provided to the object constructor and stored in an instance variable. The apply method will retrieve it later to perform its test:

public class GreaterThan implements Predicate<Integer> {
    private Integer m;
    public GreaterThan(Integer m) {
        this.m = m;
    }
    public boolean apply(Integer n) {
        return n > m;
    }
}

No changes are necessary to either the Predicate interface or to Utils.filter:

Utils.filter(new GreaterThan(4), Arrays.asList(-2, 3, 7, 1));
Utils.filter(new GreaterThan(10), Arrays.asList(100, -9, 8));