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:

input:  [3, 5, 2]
array1: [1, 3, 15]// (that is, 1, 1*3, 1*3*5)

array2: [10, 2, 1]// (that is, 1*2*5, 1*2, 1)  

output: [10, 6, 15]//(that is, 1*10, 3*2, 15*1)

Classic Java solution

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

/**
 * Imperative solution using classic (non-functional) java
 * 
 * @param input
 * @return
 */
public static int[] simpleSolution(int[] input) {
  if (input.length == 0)
    return new int[] {};
  int productSoFar = 1;
  int[] output = new int[input.length];
  int[] ascending = new int[input.length];
  int[] descending = new int[input.length];
  // ascending partial products

  int index = 0;
  do {
    ascending[index] = productSoFar;
    productSoFar = productSoFar * input[index];
    index++;
  } while (index < input.length);
  // descending partial products

  index = input.length - 1;
  productSoFar = 1;
  do {
    descending[index] = productSoFar;
    productSoFar = productSoFar * input[index];
    index--;
  } while (index >= 0);
  //now generate the output by multiplying the data

  for (int i = 0; i < output.length; i++) {
    output[i] = ascending[i] * descending[i];
  }
  return output;
}

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:

(defn array-produce [input]
    (map *
         (reductions * 1 (butlast input))
         (reverse
           (reductions * 1 (butlast (reverse input))))))

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.

Adding zip function

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:

/**
 * Combine two IntStreams using a zipper function. Will run until one of the
 * input streams is exhausted.
 * 
 * @param stream1
 * @param stream2
 * @param zipper
 * 
 * @return IntStream
 */
public static IntStream zip(IntBinaryOperator zipper, IntStream stream1,
    IntStream stream2) {
  return zip(zipper, false, 0, 0, stream1, stream2);
}

/**
 * Combine two IntStreams using a zipper function. If exhaustAll is false,
 * will run until one stream is exhausted; if true will run until both input
 * streams exhausted. If exhaustAll is true, will utilize
 * exhaustedVal1/exhaustedVal2 for zipper if one of the input streams is
 * exhausted but the other is not.
 * 
 * @param stream1
 * @param stream2
 * @param zipper
 * @param exhaustAll
 * @param exhaustedVal1
 * @param exhaustedVal2
 * @return
 */
public static IntStream zip(IntBinaryOperator zipper, boolean exhaustAll,
int exhaustedVal1, int exhaustedVal2, IntStream stream1,
IntStream stream2) {
  Objects.requireNonNull(zipper);
  Spliterator.OfInt spliterator1 =
    Objects.requireNonNull(stream1).spliterator();
  Spliterator.OfInt spliterator2 =
    Objects.requireNonNull(stream2).spliterator();

  // Zipping looses DISTINCT and SORTED characteristics

  int characteristics =
    spliterator1.characteristics() & spliterator2.characteristics()
    & ~(Spliterator.DISTINCT | Spliterator.SORTED);

  PrimitiveIterator.OfInt iterator1 = Spliterators.iterator(spliterator1);
  PrimitiveIterator.OfInt iterator2 = Spliterators.iterator(spliterator2);

  PrimitiveIterator.OfInt outputIterator = new PrimitiveIterator.OfInt() {

    @Override
    public boolean hasNext() {
      if (exhaustAll) {
        return iterator1.hasNext() || iterator2.hasNext();
      } else {
        return iterator1.hasNext() && iterator2.hasNext();
      }
    }

    @Override
    public Integer next() {
      return nextInt();
    }

    @Override
    public int nextInt() {
      if (exhaustAll) {
        return zipper.applyAsInt(
          iterator1.hasNext() ? iterator1.nextInt() : exhaustedVal1,
          iterator2.hasNext() ? iterator2.nextInt() : exhaustedVal2);
      } else {
          return zipper.applyAsInt(iterator1.nextInt(), iterator2.nextInt());
      }
    }
  };
  // Our output stream will be the size of the larger of the two input

  // streams if exhaustall is true, otherwise the smaller; -1 if unknown

  long outputSize = -1;
  if((characteristics  & Spliterator.SIZED) != 0 ){
    long size1 = spliterator1.getExactSizeIfKnown();
    long size2 = spliterator2.getExactSizeIfKnown();
    outputSize = exhaustAll ? Math.max(size1, size2) : Math.min(size1, size2);
  }

  Spliterator.OfInt outputSpliterator =
    Spliterators.spliterator(outputIterator, outputSize,
      characteristics);

  // can be run in parallel if both input streams can be run in parallel

  return StreamSupport.intStream(outputSpliterator, stream1.isParallel()
    && stream2.isParallel());
}

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:

/**
 * Functional solution 1: using static methods
 * 
 * @param input
 * @return
 */
public static int[] functionalSolution(int[] input) {
 return StreamUtil
   .zip((i, j) -> i * j,
     StreamUtil.reductions((i, j) -> i * j, 1,
       Arrays.stream(input)),
     StreamUtil.streamInReverse(
       StreamUtil.reductions((i, j) -> i * j, 1,
         StreamUtil.streamInReverse(input))
         .toArray()).skip(1)).toArray();
}

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:

/**
 * Functional solution 2: add some local variables to make it more sane
 * 
 * @param input
 * @return
 */
public static int[] functionalSolution2(int[] input) {
  IntStream ascending = Arrays.stream(input);
  IntStream descending = StreamUtil.streamInReverse(input);

  IntStream reductions1 =
    StreamUtil.reductions((i, j) -> i * j, 1, ascending);

  IntStream reductions2 =
    StreamUtil.streamInReverse(StreamUtil.reductions( 
      (i, j) -> i * j, 1, descending)
    .toArray());

  return StreamUtil
      .zip((i, j) -> i * j, reductions1, reductions2.skip(1))
      .toArray();
}

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:

/*
 * What I'd really like to do:
 *  1 Add reductions() method to Stream.  Same arguments as Stream.reduce().
 *    Returns stream of intermediate results of reduce operation.
 *
 *  2 Add reverse() method to Stream (Returns a Stream of elements in the 
 *    opposite order as encountered in this stream.  Obviously only applies to
 *    stream of finite length
 *
 *  3 Add zipWith() function to stream.  Takes another Stream and a BiFunction
 *    (2 arg function) as arguments; returns another stream by applying 
 *    finction to corresponding elements of this stream and the stream applied
 *    as an argument
 * 
 *  4 As long as we're wishing, I'd like to be able to add methods to int[]
 */
public static int[] functionalSolution(int[] input){
  input.stream(input)
    .reductions((i, j) -> i * j, 1);
    .zipWith((i, j) -> i * j,
      input.streamInReverse
        .reductions((i, j) -> i * j, 1)
        .reverse()
    .toArray();
}

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.:

int[] input = new int[]{3, 5, 2};
int[] reductions = 
  Arrays.stream(input)
        .map(reductionsMapper) //we'll figure out how to write this next

        .toArray();

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:

/**
 * Return stream of results from recursive application of function to each
 * element in the Stream except the last one. Seed value is the initial
 * value and will be returned as the first element in the resulting stream
 * 
 * @param op
 * @param seed
 * @return
 */
public static <T> UnaryOperator<T> reductionsMapper(BinaryOperator<T> op,
    T seed) {
  Objects.requireNonNull(op);

  StreamRef<T> accTotal = new StreamRef<T>(seed);

  return (t) -> {
    T returnVal = accTotal.val;
    accTotal.val = op.apply(t, accTotal.val);
    return returnVal;
  };
}

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:

/**
 * Return stream of results from recursive application of function to each
 * element in the Stream except the last one. Seed value is the initial
 * value and will be returned as the first element in the resulting stream
 * 
 * @param op
 * @param seed
 * @return
 */
public static <T> UnaryOperator<T> reductionsMapper(BinaryOperator<T> op,
    T seed) {
  Objects.requireNonNull(op);

  StreamRef<T> accTotal = new StreamRef<T>(seed);

  return (t) -> {
    T returnVal = accTotal.val;
    accTotal.val = op.apply(t, accTotal.val);
    return returnVal;
  };
}

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:

int[] input = new int[]{3, 5, 2};
Arrays.stream(input)
      .map(StreamUtil.reductionsMapper((i, j)->i*j, 1))
      .toArray();//returns (int[]) [1, 3, 15]


//or, using Integer reference type:


Integer[] input2 = new Integer[]{3, 5, 2};
Arrays.stream(input2)
      .map(StreamUtil.reductionsMapper((i, j)->i*j, 1))
      .toArray(Integer::new);//returns (Integer[]) [1, 3, 15]

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:

/**
 * Returns a IntUnaryOperator which can be used to zip another stream with
 * the stream it is applied to, using the operator provided. .
 * 
 * @param stream
 * @param mapper
 * @param nullValue
 * @return
 */
public static IntUnaryOperator intZipMapper(IntBinaryOperator mapper,
    int nullValue, IntStream stream) {
  Objects.requireNonNull(mapper);
  OfInt spliterator = Objects.requireNonNull(stream).spliterator();

  PrimitiveIterator.OfInt iterator = Spliterators.iterator(spliterator);

  return i -> mapper.applyAsInt(i,
      iterator.hasNext() ? iterator.nextInt() : nullValue);
}

/**
 * Zipper type function to allow two streams to be zipped together through
 * Stream.map() function
 * 
 * Note: function is statefull; will not work on parallel streams
 * 
 * @param zipStream
 * @param zipper
 * @param nullValue
 * @return
 */
public static <T, R> Function<? super T, ? extends R> zipMapper(
    BiFunction<T, T, R> zipper, T nullValue,
    Stream<T> zipStream) {
  return zipMapper(zipStream, zipper, nullValue, zipStream);
}
  
/**
 * Zipper type operator to allow two streams to be zipped together through
 * Stream.map() function.  Target stream argument allows zipping together
 * streams of different types, it is not actually muted or otherwise 
 * operated on
 * Note: function is statefull; will not work on parallel streams
 * 
 * @param zipStream
 * @param zipper
 * @param nullValue
 * @param targetStream
 * @return
 */
public static <T, U, R> Function<? super T, ? extends R> zipMapper(
    Stream<T> targetStream,
    BiFunction<T, U, R> zipper, U nullValue,
    Stream<? extends U> zipStream) {
  Objects.requireNonNull(zipper);
  Spliterator<? extends U> spliterator =
      Objects.requireNonNull(zipStream).spliterator();

  Iterator<? extends U> iterator = Spliterators.iterator(spliterator);

  return i ->
    zipper.apply(i, iterator.hasNext() ? iterator.next() : nullValue);
}

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:

/**
 * Does not work
 * @return
 */
public static <T> Collector<T, ?, Stream<T>> streamReverser() {
  return Collector.of(() -> {                 // collector

    Builder<T> builder = Stream.builder(); 
      return builder.build();
    }, 
    (t, u) -> Stream.concat(t, Stream.of(u)), //accumulator

    (t, u) -> {                               //combiner

      throw new IllegalArgumentException("Cannot reverse a parallel Stream");
    };
}

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):

public static <I> Supplier<Stream.Builder<I>> supplier() {
  Builder<I> builder = new Builder<I>() {
    LinkedList<I> data = new LinkedList<I>();
    int outputSize = 0;

    @Override
    public void accept(I t) {
      data.addLast(t);
      outputSize++;
    }

    @Override
    public Stream<I> build() {
      Iterator<I> outputIterator = data.descendingIterator();
      Spliterator<I> outputSpliterator =
      Spliterators.spliterator(outputIterator,
        outputSize, Spliterator.SIZED
        | Spliterator.ORDERED);
      // cannot run in parallel w/o losing order

      return StreamSupport.stream(outputSpliterator, false);
    }

  };
  return () -> builder;
}

public static <T> Collector<T, Stream.Builder<T>, Stream.Builder<T>> collector(){
  return Collector.of(
  supplier(), 
  (t, u) -> t.accept(u), //accumulator

  (t, u) ->{             //combiner

    throw new IllegalArgumentException(
      "Cannot reverse a parallel Stream");
  });
}

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:

  <R> R collect(Supplier<R> supplier,
    ObjIntConsumer<R> accumulator,
    BiConsumer<R, R> combiner);

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:

public static class IntStreamReverse {
  public static Supplier<IntStream.Builder> supplier() {
    return () -> new IntStream.Builder() {
      LinkedList<Integer> data = new LinkedList<Integer>();
      int outputSize = 0;

      @Override
      public void accept(int t) {
        data.addLast(t);
        outputSize++;
      }

      @Override
      public IntStream build() {
        Iterator<Integer> outputIterator =
          data.descendingIterator();
        Spliterator<Integer> outputSpliterator =
          Spliterators.spliterator(outputIterator,
            outputSize, Spliterator.SIZED
            | Spliterator.ORDERED);
        // cannot run in parallel w/o losing order

        return StreamSupport.stream(outputSpliterator, false)
          .mapToInt(i -> i);
      }

    };
  }

  public static ObjIntConsumer<IntStream.Builder> accumulator() {
    return (r, e) -> r.accept(e);
  }

  public static BiConsumer<IntStream.Builder, IntStream.Builder>
    combiner() {
      return (t, u) -> t.build().forEach(u::accept);
  }
}

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):

import static org.bendra.util.StreamUtil.*;
import static java.util.Arrays.stream;


/**
 * Full method chaining, Zip and reductions mapper, IntStreamReverse
 * 
 * @param input
 * @return
 */
public static int[] functionalChainedSolution(int[] input) {

  return stream(input)
      .map(intReductionsMapper((i, j) -> i * j, 1))
      .map(intZipMapper( (i, j) -> i * j, 0,
          streamInReverse(input)
          .map(intReductionsMapper((i, j) -> i * j, 1))
          .collect(IntStreamReverse.supplier(),
            IntStreamReverse.accumulator(),
            IntStreamReverse.combiner()).build()))
      .toArray();
}

Or, using reference types instead of primitives:

/**
 * Full method chaining, Zip and reductions mapper, IntStreamReverse
 * 
 * @param input
 * @return
 */
public static Integer[] functionalChainedSolution(Integer[] input) {

  return stream(input)
      .map(reductionsMapper((i, j) -> i * j, 1))
      .map(zipMapper((i, j) -> i * j, 0,
          streamInReverse(input)
          .map(reductionsMapper((i, j) -> i * j, 1))
          .collect(StreamReverse.collector()).build()))
      .toArray(Integer[]::new);
}

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.