Discussion 7: Iterators and Lambda Expressions

The goal of today’s discussion is to practice using lambda expressions and iterators. It is often useful to have a way to iterate through a data structure, but only return elements that satisfy a certain condition. In this discussion, you will implement an iterator that simultaneously traverses and filters the elements of a singly linked list. We’ll use a Predicate functional interface, allowing the client to pass in a lambda expression to define how the list should be filtered. This gives an easy way for clients to define a filtered iteration without having to allocate a new data structure.

Learning Outcomes

  1. Describe the use cases for the Iterable and Iterator interfaces.
  2. Implement iterators for a given data structure class and use iterators as a client.
  3. Identify and define functional interfaces and implement them using lambda expressions.

Reminder: Discussion Guidelines

The work that you complete in discussion serves as a formative assessment tool; it offers the opportunity to assess your understanding of the material and for our course staff to get a “pulse” on how things are going, so we can make adjustments in future classes. Your grade in discussion is based on your attendance, active participation, and completion of that day’s activity. More information about the grading and expectations can be found in the syllabus.

Since discussion activities are not graded for correctness, we do not restrict what resources you may use to complete them, which include notes, books, unrestricted conversations with other students, internet searches, and the use of large language models or other generative AI. We advise you to be pragmatic about your use of these resources and think critically about whether they are enhancing your learning. Discussion activities are intended to serve as “strength training” for programming tasks we will expect on assignments and exams (and that you will encounter in future courses and careers), and their main benefit comes from thinking critically to “puzzle” them out.

Exercise 1: Warmup: Predicates and Lambda Expressions
In today's discussion, you'll write an Iterator that offers a "filtered" view of a list to the client. We would like a way for the client to be able to specify how this filter should work. In other words, they should be able to pass a parameter to this iterator that somehow encodes which elements should be "accepted" through the filter and returned by the iterator, and which elements should be "rejected" by the filter and not returned. This parameter that is being passed in models a behavior: it says how the program should behave when presented with each of the elements. We saw in lecture that functional interfaces offer a good way to model a behavior as a type. Conveniently, Java provides us with the exact functional interface that we need, its generic Predicate interface. This interface defines a single (non-static, non-default) method, test(), with the following specifications: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

/** 
 * Represents a predicate (boolean-valued function) of one argument.
 * This is a functional interface whose functional method is `test()`.
 */
@FunctionalInterface
public interface Predicate<T> {
  /**
   * Evaluates this predicate on the given input argument `t`.
   * Returns `true` if `t` matches the predicate, otherwise returns `false`.
   */
  boolean test(T t);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

/** 
 * Represents a predicate (boolean-valued function) of one argument.
 * This is a functional interface whose functional method is `test()`.
 */
@FunctionalInterface
public interface Predicate<T> {
  /**
   * Evaluates this predicate on the given input argument `t`.
   * Returns `true` if `t` matches the predicate, otherwise returns `false`.
   */
  boolean test(T t);
}
The test() method accepts a parameter of type T (the same generic type as the list), and returns whether that object matches the predicate, or, in other words, is "accepted" by the filter. Before we move on to the main task of designing our filtering iterator, let's take a few minutes to get acquainted with the Predicate interface in a simpler setting.

Download Starter Code download
For this discussion, you'll be submitting your code.
(a)
First, let’s see how to use a variable with a Predicate type within a method. In the PredicateWarmUp class, implement the filterArray() method. This method takes in an array of ints and a Predicate object, and prints every element in the array that satisfies the predicate (e.g., the predicate’s test() method returns true for the respective element).
(b)
Now, let’s see how we can instantiate a Predicate using a lambda expression. Complete the definition of the PredicateWarmUp.main() method. This should call filterArray() to print out the even elements of elems. The second argument to filterArray() should be a lambda expression (providing the filter by defining the Predicate’s test() method).
Exercise 2: Implementing FilteredIterator
Next, you implement the nested FilteredIterator class within the SinglyLinkedList. This will behave similarly to the "normal" iterators that we discussed; however, the next() method will only return elements that satisfy the Predicate passed into its constructor.

(a)
Implement the FilteredIterator.advance() helper method so that it conforms to its specifications. The code that you write will make use of the Predicate field similarly to the previous exercise.
(b)
Implement the FilteredIterator constructor. This should initialize all the fields to the appropriate values to establish the class invariant.
(c)
Implement the hasNext() and next() methods for the FilteredIterator. These should behave similarly to a normal forward iterator, except next() should never return an element that does not satisfy the predicate field, and hasNext() should behave accordingly.
(d)
Test your solution using the provided unit tests in FilteredIteratorTests.java. One of these tests will fail as it tests the FilterDemo.main() method that you have not yet implemented.
Exercise 3: Using an Iterable
Now, we have an easy way to write a filtered loop whose filter can be defined with a lambda expression. Next, you'll write some client code to see this in action. Before jumping into this, take a look at the SinglyLinkedList.filter() method that was provided in the starter code: 
1
2
3
4
5
6

/**
 * Returns a filtered Iterable based on `predicate`.
 */
public Iterable<T> filter(Predicate<T> predicate) {
  return () -> new FilteredIterator(predicate);
}

1
2
3
4
5
6

/**
 * Returns a filtered Iterable based on `predicate`.
 */
public Iterable<T> filter(Predicate<T> predicate) {
  return () -> new FilteredIterator(predicate);
}
There's a lot going on here to unpack! The return type of this method is Iterable (which is the most general return type that we can declare that can be used within an enhanced for loop). However, if we look at the method definition, it returns a lambda expression. Iterable is not only an interface, it's a functional interface; it has exactly one (non-static, non-default) method. Therefore, we can use a lambda expression to express a definition of its iterator() method, which has no parameters and returns a reference to an Iterator.

Complete the definition of the FilterDemo.main() class. This method should use the filter() method to iterate over only the positive elements of the list and print them to the console, one per line.

Submission

At the end of class, your group’s primary author should upload the following files to Gradescope:

  1. PredicateWarmup.java
  2. SinglyLinkedList.java
  3. FilterDemo.java

Make sure that all other members of the group are tagged on the submission.