Tag Archives: iterate

Finite sequence generators in Java 8

… and introducing default methods.

Last time we looked at generators, and more specifically those generating an infinite sequence. We saw that there were several ways to achieve this:

  • The older Java 7 way with an iterator like class
  • Using Stream’s iterate method
  • Using Stream’s generate method

We also saw that when using a Stream we had to use the limit method on our infinite sequence otherwise it would keep generating and the program couldn’t continue. The problem with using limit was that once we’d got the values, we couldn’t use the stream again to get more. To solve this problem, we used an IntSupplier and created several streams with it to process batches of values.

What if the sequence we wanted to process was finite. We want to avoid buffering up values in advance. We also want to consume the sequence without knowing up front how many values it will return because of reasons such as:

  • We can’t work it out or it’s difficult to
  • There is a random element
  • We want to decouple the generating function from stream doing the consuming

We saw a simple finite sequence with our Hello World! example in the first article. In this case we were not generating the sequence with a function, we were instead processing a pre-initialised list. We also saw we could use an iterator when we discussed infinite sequences, but went on to discuss other ways. We’ll see that in this case, we are virtually forced into the Iterator solution.

Let’s take a simple sequence which we can’t know the length of. We’ll simulate a game where the idea is to keeping throwing a die until we get a six. First we’ll start with a non-functional implementation:

public class SixGame
{
	public static class DieThrowIterator implements Iterator<Integer>
	{
		private int dieThrow = 0;
		private Random rand = new Random(System.nanoTime());

		@Override
		public boolean hasNext()
		{
			return dieThrow != 6;
		}

		@Override
		public Integer next()
		{
			dieThrow = Math.abs(rand.nextInt()) % 6 + 1;
			return dieThrow;
		}
	}

	public static void main(String args[])
	{
		DieThrowIterator dieThrowIterator = new DieThrowIterator();

		while (dieThrowIterator.hasNext())
		{
			System.out.println("You threw a " + dieThrowIterator
                                  .next());
		}
	}
}

(Note our random number generation is not very robust, but for a simple demonstration it will do).

Let’s try to use a Stream. We can’t use Stream’s iterate function because it doesn’t allow a stop condition. Also an IntSupplier with generate is not an option unless we want to use limit(1) and create a stream for each die throw, when we might as well not use a stream at all.

If we look under the hood at the implementation of IntStream’s generate function we see that it creates an InfiniteSupplyingSpliterator. This has a problem for us – the tryAdvance function always returns true meaning we can never stop.

We could implement our own Spliterator where our tryAdvance checks for a stop condition. We can’t simply extend InfiniteSupplyingSpliterator and override the tryAdvance method since it’s an inner class of a default access class. So the only way is a cut and paste job rather than inheritance. I’m very nervous about copying large parts of code which might change in future versions; this is saying to me it’s not what was intended. We should look for other ways first.

Let’s look to see how List does its streaming. List’s streaming comes from inheriting Iterable. To create an Iterable we only need to implement its iterator() function – for the example let’s do so as an inner-class:

	public static class DieThrowIterable implements Iterable<Integer>
	{
		@Override
		public Iterator<Integer> iterator()
		{
			return new DieThrowIterator();
		}
	}

We can then stream:

	public static void main(String args[])
	{
		Stream<Integer> stream = StreamSupport.stream(
				new DieThrowIterable().spliterator(), false);

		stream.map(i -> "You threw a " + i).forEach(System.out::println);
	}

Wait a moment… Iterable is an interface, yet it has a spliterator() method implemented. How can that be?

If we look at the interface, there is indeed a spliterator() method creating a new spliterator for us. If we also look closely, we see the default keyword. This was added in Java 8 (cunningly default is already a reserved word for switch statements so it won’t break old code). When we write interfaces we can provide default methods already implemented. Now some people might have reservations about this as it’s turning an interface in to effectively an abstract class. There are some good reasons and advantages this gives us:

  • It avoids having to create abstract classes to implement interfaces to supply default methods. Thus there is less boiler-plate to write, and also prevents the consumer of the API implementing the interface when we expected the abstract class to be used instead.

  • It helps with multiple inheritance issues (inherting from two or more classes which C++ supports, but not Java). In Java, the problems with multiple inheritance were avoided by allowing only single inheritance from classes, but we can implement as many interfaces as desired. Problem is we had to implement large portions of those interfaces in each class that used them – a real pain.

  • Our API vendors can also now add new methods to interfaces without breaking old code. This is one reason we see a default method here. A new interface would make the JDK even larger and make things more complicated.

  • Lambda expressions bind to interfaces with one single method left to implement. If there were more we couldn’t do this binding. We’ll look at this in a future article.

Note: If we implement more than one interface with an identical default method, and we do not override it by implementing in the class or a parent class, this is an error. Whether eventually it’ll be possible to use Scala-like mix-in traits is an interesting question.

So using Iterable is one way to do finite sequence generators, although the documentation accompanying the default spliterator() method suggests it should be overridden for better performance. In a later article we’ll come back and look at spliterators in some more detail.

In the next article we’ll look another couple of ways to implement finite sequence generators, one good, and one we should avoid.

Advertisements

Generators with Java 8

Today we’ll look at creating generators. In simple terms, a generator is a function which returns the next value in a sequence. Unlike an iterator, it generates the next value when needed, rather than returning the next item of a pre-generated collection. Some languages such as Python support generators natively via keywords such as yield. When a generator’s next value is requested in Python, the generator function continues to run until the next yield statement, where a value is returned. The generator function is able to continue where it left off which can be quite confusing for the uninitiated. So how to do something similar in Java?

We saw in the last article that we can use an IntStream to generate a simple set of numbers, but we had to generate them all up front. That’s fine if we know how many we’re going to need. What if we don’t, and we want to be able to get the next whenever we like? This is where a generator comes in.

Let’s choose a simple infinite sequence, the square numbers. In a standard Java implementation we’d end up with something like the following:

public class Squares
{
        private int i = 1;

        public int next()
        {
                int thisOne = i++;
                return thisOne * thisOne;
        }

        public static void main(String args[])
        {
                Squares squareGenerator = new Squares();

                System.out.println(squareGenerator.next());
                System.out.println(squareGenerator.next());
                System.out.println(squareGenerator.next());
        }
}

This prints the first three square numbers. Note we could have gone further and implemented this as an iterator.

What we have here is an example of lazy evaluation in a non-functional style. Wikipedia defines lazy evaluation as: ‘In programming language theory, lazy evaluation, or call-by-need is an evaluation strategy which delays the evaluation of an expression until its value is needed’. Lazy evaluation is useful because we don’t need to worry about infinite sequences, performing computationally expensive operations up-front, and about storage.

Let’s expand on the example to allow getting a batch of results. This is easy – create a nextN function which calls next() a number of times and returns the results in say a List:

public class Squares2
{
        private int i = 1;

        public int next()
        {
                int thisOne = i++;
                return thisOne * thisOne;
        }

        public List<Integer> nextN(int n)
        {
                List<Integer> l = new ArrayList<>();

                for (int i = 0; i < n; i++)
                {
                        l.add(next());
                }

                return l;
        }

        public static void main(String args[])
        {
                Squares2 squareGenerator = new Squares2();

                squareGenerator.nextN(10).forEach(System.out::println);
        }
}

A few points:

  • Notice in the nextN function there is the empty diamond in the new ArrayList statement. This was added in Java 7 to save having to state the type both on the left and the right hand side; the compiler now works it out.
  • List is an Iterable, and Iterable now has a forEach() method which was added in Java 8. We could use stream() as before to create a stream, but if all we want to do is pass the contents to a function forEach() does nicely.

Now, to save having to write nextN for every sequence we make, we could create a new type which extends Iterator providing the nextN function.

The only problem we face here is that we have to save the batch in a list before we can operate on it. Java 8 provides another way. Let’s go back and start again with the following code:

public class Squares3
{
        public static void main(String args[])
        {
                IntStream.rangeClosed(1, 10).map(i -> i * i)
                         .forEach(System.out::println);
        }
}

This uses IntStream to get the indexes of the sequence in a stream and calls map to convert them into their squares. The problem is that to get more squares than the tenth we need to duplicate the pipeline and start it off from the right place. Let’s look at another way without using a range:


        public static void main(String args[])
        {
                IntStream myStream = IntStream.iterate(1, i -> i + 1);

                myStream.limit(10).map(i -> i * i)
                                  .forEach(System.out::println);
        }

This also generates the first 10 square numbers. This time it uses the iterate function. This takes two parameters, the first is our initial value, and the second is a function defining how to get to the next value from the previous. It’s a good place to use a lambda function. We can even dispense of the map function since we can undo squaring easily in iterate to get what the last index was:

        public static void main(String args[])
        {
                IntStream myStream = IntStream.iterate(1,
                        i -> ((int) Math.pow(Math.sqrt(i) + 1, 2)));

                myStream.limit(10).forEach(System.out::println);
        }

This solves one of the problems of having to buffer beforehand. However, we need to use the limit operator on the stream to limit it to 10 items, otherwise it would keep on going. Unfortunately this is a problem, since once we’ve got the 10 the stream is ‘operated on’ and we can’t use it again to generate more. If we try, we get an IllegalStateException. We’d have to create another stream to get more.

So how do we get around the problem of the stream being used up? Instead of using IntStream’s iterate function, we can use generate instead. IntStream’s generate function takes an instance of an IntSupplier. IntSupplier has a getAsInt() function which returns the next int in the sequence which is very much like our next() function. Here is an example that prints the first 20 square numbers in two batches:

public class SquaresGenerator
{
        private static class SqSupplier implements IntSupplier
        {
                int i = 0;

                @Override
                public int getAsInt()
                {
                        i++;
                        return i * i;
                }
        }

        public static void main(String args[])
        {
                SqSupplier sqSupplier = new SqSupplier();
                IntStream myStream = IntStream.generate(sqSupplier);
                IntStream myStream2 = IntStream.generate(sqSupplier);

                myStream.limit(10).forEach(System.out::println);
                myStream2.limit(10).forEach(System.out::println);
        }
}

Again we’re using limit to stop the stream continuing indefinitely. However unlike last time, although the stream is used up, the generator still survives and can be used again. No buffering needed either, just keeping hold of the supplier. The only downside vs the old Java way is that we have to use Streams to get sequence members, although this comes with other benefits such as parallelism which we’ll see in a later article.

Overall, there are several ways to generate a sequence and which we chose may depend on our needs. Using an IntSupplier is a good way to integrate with the rest of the Java 8 functional programming support.