Intent

To iterate through the elements of a sequence in order, without having to index into it

Overview

An iterator is an object that allows us to iterate over all the objects in a sequence. It does so by maintaining an internal bit of state that keeps track of where in the sequence the iterator is currently. At its simplest, an implementation of Iterator just requires a method that returns the next item in the sequence, with some sentinel value returned when there are no more items.

Most implementations have a separate method to check to see if the iterator has any more items, rather than using a sentinel to check. Some implementations of Iterator allow the underlying collection to be modified by removing the current item.

Also Known As

Cursor
Enumerator

Functional Replacement

In this section, we’ll focus on replacing an iterator with a combination of higher-order functions and sequence comprehensions. A sequence comprehension is a clever technique that lets us take one sequence and transform it into another in some sophisticated ways. They’re a bit like the map function on steroids.

Many basic uses of Iterator can be replaced by simple higher-order functions. For instance, summing a sequence can be done in Clojure using the reduce higher-order function.

Other, more complex uses can be handled with sequence comprehensions. Sequence comprehensions provide a concise way to create a new sequence from an old one, including the ability to filter out unwanted values.

In this section we’ll stick with the uses of Iterator that can be expressed using a Java foreach loop. Other, less common uses can be replaced by the functional patterns Pattern 12, ​Tail Recursion​, and Pattern 13, ​Mutual Recursion​.

Sample Code: Higher-Order Functions

Let’s start by looking at a grab bag of simple uses of Iterator that can be replaced with higher-order functions. First we’ll look at identifying the vowels in a string, then we’ll take a look at prepending a list of names with "Hello, ", and finally we’ll sum up a sequence.

We’ll look at these examples first in an imperative style written in Java, and then we’ll collapse them into a more declarative style in Scala and Clojure.

Classic Java

To identify the set of vowels in a word, we iterate through the characters and check each character against the set of all vowels. If it’s in the set of all vowels, we add it to vowelsInWord and return it. The code below, which assumes an isVowel helper method, illustrates this solution:

There’s a higher-level pattern here: we’re filtering some type of element out of a sequence. Here it’s vowels in a string, but it could be odd numbers, people named “Michael” or anything else. We’ll exploit this higher-order pattern in our functional replacement, which uses the filter function.

Next up, let’s discuss prepending a list of names with the “Hello, ” string. Here we take in a list of names, iterate through them, prepend “Hello, ” to each name, and add it to a new list. Finally we return that list.

The code below demonstrates this approach:

Again, there’s a higher-level pattern hiding here. We’re mapping an operation onto each item in a sequence, here prepending a word with the “Hello, ” string. We’ll see how we can use the higher-order map function to do so.

Let’s examine one final problem: summing up a sequence of numbers. In classic Java, we’d compute a sum by iterating through a list and adding each number to a sum variable, as in the code below:

This type of iteration is an example of another pattern, performing an operation on a sequence to reduce it to a single value. We’ll take advantage of that pattern in our functional replacement using the reduce function and a closely related function known as fold.

In Scala

Let’s take a look at the first of our examples, returning the set of vowels in a word. In the functional world, this can be done in two steps: first we use filter to filter all the vowels out of a word, and then we take that sequence and turn it into a set to remove any duplicates. To do our filtering, we can take advantage of the fact that Scala sets can be called as predicate functions. If the set contains the passed-in argument, it returns true; otherwise it returns false, as the code below shows:

Now we can use the isVowel from above, along with filter and toSet, to get a set of vowels out of a string:

Here we can see it in action, filtering vowels out of a string:

Our next example—prepending a list of names with “Hello, ”—can be written by mapping a function that does the prepending over a sequence of strings. Here, mapping just means that the function is applied to each element in a sequence and that a new sequence is returned with the result. Here we map a function that prepends the string "Hello, " to each name in a sequence:

This does the job, as the code below shows. The Scala REPL inserts commas between elements in a sequence, so it’s putting an additional comma between each of our greetings.

Finally, our last example—summing a sequence. We’re using an operation, in this case, addition, to take a sequence and reduce it to a single value. In Scala, the simplest way to do this is to use the aptly named reduce method, which takes a single argument, a reducing function.

Here we create a reducing function that adds its arguments together, and we use it to sum a sequence:

Let’s take a look at it in action:

That’s it—no iterating, no mutation, just a simple higher-order function!

In Clojure

Our first example takes advantage of the same trick we used in Scala, where a set can be used as a predicate function. If the passed-in element is in the set, it’s returned (remember, anything but false and nil is treated as true in Clojure); otherwise nil is returned.

Here we take advantage of that property of Clojure sets to define a vowel? predicate, which we can then use with filter to filter the vowels out of a sequence. We then use Clojure’s set function to construct a new set from an existing sequence. The code below puts it all together:

Now we can use it to filter out sets of vowels from a word:

Next up is our friendly little hello prepender, prepend-hello. Just like the Scala example, we simply use map to map a function that prepends "Hello, " to each name in a sequence of names. Here’s the code:

We can use this to generate a set of greetings:

Finally, let’s look at how we’d sum a sequence in Clojure. Just like Scala, we can use the reduce function, though we don’t have to create our own function to add integers together as we did in Scala: we can just use Clojure’s + function. Here’s the code:

And here we are using it to sum a sequence:

Those unfamiliar with Clojure might find it a bit odd that the + is just another function that we can pass into reduce, but this is one of the strengths of Clojure and Lisps in general. Many things that would be special operators in other languages are just functions in Clojure, which lets us use them as arguments to higher-order functions like reduce.

One note on reduce in Clojure and Scala: While we were able to use them the same way here, they’re actually somewhat different. Scala’s reduce operates over a sequence of some type, and it returns a single item of that type. For instance, reducing a List of Int will return a single Int.

Clojure, on the other hand, allows you to return anything at all from its reduce function, including another collection of some sort! This is more general (and often very handy), and Scala supports this more general idea of reduction under a different name, foldLeft.

It’s usually easier and clearer in Scala to use reduce when you truly are reducing a sequence of some type to a single instance of that type, and to use foldLeft otherwise.

Sample Code: Sequence Comprehensions

Both Scala and Clojure support a very handy feature called a sequence comprehension. Sequence comprehensions give us a handy syntax that lets us do a few different things together. Much like the map function, sequence comprehensions let us transform one sequence into another. Sequence comprehensions also let us include a filtering step, and they provide a handy way to get at pieces of aggregate data, known as destructuring.

Let’s take a look at how we’d use sequence comprehensions to solve a delicious little problem. We’ve got a list of people who asked to be notified when our new restaurant, The Lambda Bar and Grille, opens, and we’d like to send them an invitation to a grand-opening party.

We’ve got names and addresses, and we figure that people who live closest to the Lambda will be more likely to come, so we’d like to send invitations to them first. Finally, we’d like to filter out people who live so far away that we’re entirely sure they won’t come.

We decide to solve the problem like so: we’ll put our customers into groups based on zip codes, and we’ll send invitations to the groups of people in zip codes closest to our restaurant first. Additionally, we’ll constrain ourselves to a small group of close zip codes.

Let’s see how to solve this problem. We’ll start, as always, with the iterative solution in Java, and then we’ll move onto functional ones using sequence comprehensions in Scala and Clojure.

Classic Java

In Java, we create a Person and an Address in the customary JavaBean format, and we create a method, peopleByZip, that takes in a list of people, filters out the ones who don’t live close enough, and returns a map keyed off zip codes that contains lists of people in each zip code.

To do this we use a standard iterative solution with a couple of helper methods. The first, addPerson, adds a person to a list, creating the list if it doesn’t already exist, so we can handle the case where we come across the first person in a zip code.

The second, isCloseZip, returns true if the zip is close enough to the Lambda Bar and Grille to get an invite to the party, and false otherwise. To keep the example small, we’ve hard-coded just a couple of zip codes in there, but since we’ve factored that check out into its own method, it would be easy to change it to pull from some dynamic data source of zip codes we care about.

To solve the problem, we just iterate through the list of people. For each person, we check to see if he or she has a close zip code, and if yes we add them to a map of lists of people keyed off of zip codes called closePeople. When we’re all done with our iteration, we just return the map. This solution is outlined below:

This is a fairly simple data transformation, but it takes quite a bit of doing in an imperative style since we need to muck about with adding elements to the new list, and we don’t have a first-class way of filtering elements from the existing one. The more declarative sequence comprehensions help us bump up the level of abstraction here. Now let’s take a look at Scala’s version.

In Scala

In Scala, we can use Scala’s syntax for sequence comprehensions, the for comprehension, to generate our greetings in a cleaner way. We’ll use case classes for our Person and Address, and we’ll write a for comprehension that takes in a sequence of Person and produces a sequence of greetings.

For comprehensions are handy for this for a few reasons. The first is that we can use Scala’s pattern-matching syntax inside of them, which gives us a concise way to pick apart a Person into a name and an address.

Second, for comprehensions let us include a filter directly in the comprehension itself, known as a guard, so we don’t need a separate if statement to filter out people with the wrong zip codes. Finally, for comprehensions are intended to create new sequences, so there’s no need to have a temporary list to accumulate new values into; we simply return the value of the comprehension.

With a for comprehension, we’ll still use a helper isCloseZip method, but we’ll use it as part of a guard in the for comprehension itself, and we’ll do away with the mutable list of greetings from the Java solution entirely, since the result we want is just the value of the for comprehension itself.

The code for the entire solution is below:

One thing that may not be obvious when using for comprehensions is how to deal with situations when we absolutely need side effects. Since we’re programming in the functional style this should be fairly rare. As we saw above, we don’t need a mutable list to generate our list of greetings. One simple use of side effects that we still need in the functional world is printing to the console.

Here we’ve rewritten the example to just print the greetings to the console, rather than gathering them up into a sequence:

We’ve only touched on the basics of Scala’s for comprehensions here; they’re very powerful beasts. They can be used with multiple sequences and multiple guards at the same time, among several other features, but the ones that we’ve covered here let us handle the most common cases where we’d use the Iterator pattern.

In Clojure

Clojure also has built-in sequence comprehensions using the for macro. Just as in Scala, the primary point of a Clojure sequence comprehension is to take one sequence and transform it into another with built-in filtering. Clojure’s sequence comprehensions also provide a handy way of pulling apart aggregate data with destructuring.

Since Clojure and Scala’s sequence comprehensions are similar, at least for this basic usage, the structure of the solution looks pretty much the same. We’ve got a close-zip? function that takes advantage of Clojure’s handy set-as-function feature, and a generate-greetings function that consists of a single for statement.

The for statement uses close-zip? to filter out people outside of the zips we care about, and then it generates a greeting to the people who are left. The code is below:

Clojure also has a way to use a sequence comprehension-like syntax for side effects, though Clojure separates it out into a doseq macro. Here we use doseq to print our list of greetings rather than gather them up:

Scala and Clojure’s sequence comprehensions are similar in some respects, though not all. Scala’s for statement is generally used more pervasively, and often in ways that seem surprising to the uninitiated. For instance, the for statement can be used in conjunction with Scala’s option type to provide an elegant solution to problems that would require lots of null checks in Java, as we cover in Pattern 8, ​Replacing Null Object​.

Also, while Scala’s pattern matching and Clojure’s destructuring have some similarity, both allow us to pick apart aggregate data structures; pattern matching in Scala is less flexible than Clojure’s destructuring. Destructuring lets us pick apart arbitrary maps and vectors, while Scala’s pattern matching is confined to case classes and a few other constructs that are statically defined at compile time.

Discussion

One nonobvious difference between Iterator and the solutions we covered in this chapter is that Iterator is fundamentally imperative because it relies on mutable state. Every iterator has a bit of state inside it that keeps track of where the iterator is currently. This can get you in trouble if you start passing iterators around and part of your program unexpectedly advances the iterator, affecting another part.

In contrast, the solutions we’ve gone over in this chapter rely on transforming one immutable sequence into another. In fact, the sequence comprehensions we went over are both examples of a technique popularized by the highly functional language Haskell that is known as monadic transformations, which rely on a concept from category theory known as monads.

Explaining monads is a bit of a cottage industry among functional programmers and has inspired many a blog post attempting to explain monads by analogy to, among other things, burritos, elephants, writing desks, and Muppets. We won’t put you through another such explanation here; it’s not necessary to understand monads to use sequence comprehensions, and neither Scala nor Clojure particularly emphasize the monadic nature of their respective comprehensions.

At a very high level though, one of the things monads do is provide a way to program in a very functional style by transforming immutable data in a pipeline rather than relying on mutable state. Readers curious about monads should check out the excellent Learn You a Haskell for Great Good! A Beginner’s Guide [Lip11].

For Further Reading

Design Patterns: Elements of Reusable Object-Oriented Software [GHJV95]—Iterator

Java Standard Library^[5]

Related Patterns

Pattern 12, ​Tail Recursion​

Pattern 13, ​Mutual Recursion​

Pattern 14, ​Filter-Map-Reduce​