# Introduction

In some earlier articles I looked at ways to provide additional functions for maniplulating Java 8 Streams, specifically replicating a Lisp reductions function (producing the intermediate results from a reduce operation) and creating a Stream from an array/list in reverse order. We did this through writing the StreamUtil.streamInReverse() and StreamUtil.reductions() static methods. In this article we write some more functions and look at how they can be used in an advanced algorithm, attempting to address some of the shortcomings we encounter.

# Problem Statement

This is a brain teaser algorithm, which I like because it requres some non-standard idioms to solve. The problem is to write a method which takes an array of positive integers as its input (specifically no zeros), and return an array of the same length, where each index of the return array equals the product of all the elements in the input array except the corresponding one.

So for example, if the input is [3, 5, 2] the method should return [10, 6, 15]. There is a fairly easy way to solve this is by multiplying the entire input array, and then produce the output by dividing the product by each element in the input. Which brings us to the part which makes the problem challenging: do it without using the division operator!

# Solution algorithm

The problem can be solved by the following algorithm:

1. Create an array starting with 1 and then values generated by recursively multiplying the running total by each element in the input in ascending order except the last one.
2. Create another array ending with 1 and with values generated by recursively multiplying the running total by each element in the input in descending order except for the first one
3. Create the output array by multiplying the elements in the arrays 1 and 2 by each other.

Graphically, this looks like:

# Classic Java solution

The algorithm can be implemented iteratively without too much trouble, but like most things Java it takes a lot of code:

# Lisp solution

For the question of whether a functional approach can yield a more elegant solution, we can turn to Lisp. Here is a clojure implementation of the algorithm:

Note that for step 2 we must reverse the list, generate reductions, and then reverse the result. Also note that reductions returns 1 more element than we want because it includes the final total as well as the intermediate results.

Imperitive vs functional programing is a broad topic, but in this case the functional approach looks superior - less boilerplate, just pure logic. And its easy to follow.

In implementing this algorithm in Java, we can make use of both of the functions defined in earlier posts; reductions to generate the intermediate results as well as streamInReverse. In addition we need a means of joining two streams to produce a new one. In the Early Access b93 JDK there was a function java.util.stream.Streams.zip which could do this but has been removed (in fact java.util.stream.Streams is now non-public and final - thanks Oracle). Many libraries do include this function though; here is mine from org.bendra.util.StreamUtil:

Again, this is a static function in a utility class.

# Functional Java solution - first try

So, with these in our tool chest, here is the most straightforward implementation:

If you have trouble following that I don’t blame you because I can’t follow it either (and I wrote it). The problem is the mix of Java 8 method chaining (daisy-chain syntax), along with static functions on StreamUtil (requred, as noted earler, because Java lacks a facility to add mixins to existing classes). So we have to keep jumping from the end of a function call (e.g. Array.stream(), Stream.toArray(), Stream.skip()) to the enclosing parentheses (StreamUtil.streamInReverse(), StreamUtil.reductions(), StreamUtil.zip()) and it gets unreadable fast.

# Functional Java solution - take two

This can be somewhat improved by using some local variables:

I would subjectively rate this solution as “not bad”, perhaps not as clean as lisp, but I’d really like to use method chaining and avoid local variables entirely.

# Functional Java solution - wish list

What I’d really like is to be able to use method chaining throughout, but for this we’d have to be able to add methods to a class (like Scala does with Traits, Undescore.js with extends, etc.). In this hypothetical Java-topia I’d write my method something like this:

# Functional Java solution - how close can we come?

My wishlist will never happen. Java does not have any facility to add methods to existing classes, and Oracle has an awful habit of making its implementation classes final and/or private so we can’t even pretend. However the Stream interfaces (including IntStream et. al.) do have some functions that offer a method signature similar to what we want, and since they accept a functional interface as an argument they allow us considerable control over processing. We can use these to approximate what we want.

# Reducing through map()

The Stream.map() function returns a stream of equal size to the input, with a function applied to each element encountered. In an earlier article, we used a map function with some internal state to write a static reductions() function . This suggests there could be an alternative approach for our purposes: re-imagen the reductions() function not as a Static method, but as normal map operation with a recursively reducing mapper function, e.g.:

So what would our reductionsMapper look like? I have written two versions of the function: one which takes an argument as initial (seed) value, second of which uses the first value in the stream as the seed value:

Note also that the seed(initial) value provided as an argument.
This function is for an IntStream; the code for reference types is slightly different:

The output Stream will be of the same type as the input; this is consistant with Stream.reduce().

For a typical use case, say multiplying the elements it will look like this:

Of course the amount of code can be reduced with a static import of functions.

# Zipping through map()

The zipper function above, like many others you can find elsewhere, is a static function which takes two streams as input. In order to preserve the method chain, zip must be done as a method on one stream, taking the second stream as an argument. Again we will use map(); again there are some constrains on this approach:

1. Any zipper function will have to deal with the possibility that one stream has more elements than the other
2. The return from map() is always a stream with as many elements as the input stream

Therefore our function will take an additional parameter; namely the intValue to use if the second stream is exhausted before we are done mapping. If the second stream is longer there is no problem here because map() will return when the first stream is exhausted. Here is the implementation for IntStream and Stream:

# Reversing a stream

To replicate the functionality of the lisp reverse function, we have to gather the elements in a Stream then re-emit them into a new stream with the reverse ordering (and obviously this presumes an ordered, finite stream). Stream.sort() will reorder elements by their natural ordering but there is no function to preserve/modify the existing ordering of a Stream.

# Collector and the collect() function

The normal facility for consuming streams and producing other objects (or any kind) is the function collect()A collection operation consists of three parts:

1. A builder - returns a new instance of the return type.
2. An accumulator - takes a single element in a stream and applies it to the return value.
3. A combiner - combines together two instances of the return type. Neccesary for when the input stream has been split for parallel processing. In this case it should result in an error since it makes no sense to reverse a Stream of elements which are not encountered in a predictable order.

For Stream these three emements can be combined into a Collector object; for streams of primitives you have to specify them separately.

The most obvious and streightforward approach would be to write a Collector which will take a Stream’s elements as a parameter and returns a Stream of those same elements, which entails:

1. Builder - As this is parameterized and can return any reference, ours creates a new Stream of the appropriate type
2. Accumulator - turns a single element of the type and combines it with existing stream (with the new element in front)
3. Combiner - throw exception (see above)

This was my attempt at this:

Unfortunately this does not work. The collect() method calls the accumulator once for each element as they are collected, using the same object as the second argument (the return value from the accumulator is apparently not used anywhere). Since Stream.concat() closes the stream, it will throw an exception the second time it is used.

# Collecting a Builder

Instead, what we have to do is create a collector which returns a Builder which will build our stream. This isn’t hard but creating the required classes is verbose; it also means we will have to call build on the resulting builder to get our Stream (for a reference type Stream this time):

# Collecting a Builder…for IntStream

There is one more wrinkle for us because in our case we need to manupulate an IntStream rather than a Stream of reference objects. An easy solution would be to box/unbox the stream, but to keep things pure let’s go ahead and see what it will take to manipulate the existing IntStream. Unfortunately there’s no IntCollector; the method signature for IntStream.collect is:

As a result, we have to separately provide the supplier, accumulator, and combiner. To make the API neater we’ll enclose them all within a static inner class:

# Putting it all together

Now we have all the pieces we need to implement the original algorithm using method chaining. Here is what it looks like (using static imports to make things neater):

Or, using reference types instead of primitives:

# Conclusions

Method chaining can combined with functional programing to be very elegant. In many cases they can produce cleaner solutions to advanced algorithms than imperative programing. But the base Java classes only provide a limited number of methods and going beyind their targeted use cases require, shall we say, creative use of functional interfaces.