converting a Haskell function into java "function"

Question

I have this function in Haskell, and I am wondering how it can be converted to Java, especially using streams:

build = [(w,m,n,g) | w <- [240..1280], m <- [2,4..20], n <- [2..100], g <- [240..1280], ((w - 2*m - n*g) `mod` (n+1) == 0), n*g+2*m <= w, n*g <= w]

Answer 1

(I'm not a Haskell expert, but I know enough to be dangerous.)

The example code given has several Haskell constructs that map reasonably well into Java constructs:

• A Haskell list is lazy, so it corresponds to a Java Stream.

• The ranges used are of integers, so they correspond to IntStream. For example, [240..1280] corresponds to IntStream.rangeClosed(240, 1280).

• A range with a step has no direct correspondence in Java, but it can easily be computed; you just have to do a bit of arithmetic and then map the values from the sequential range to the one with steps. For example, [2, 4..20] can be written as

  IntStream.rangeClosed(1, 10).map(i -> 2 * i)
  

• A condition on a list comprehension corresponds to filtering a stream through a predicate.

• A comprehension with multiple generators corresponds to flatmapping of nested streams.

• There is no general way to represent tuples in Java. Various third party libraries provide tuple implementations with varying tradeoffs regarding generics and boxing. Or, you can just write your own class with the fields you want. (This can be quite tedious if you use lots of different kinds of tuples, though.) In this case, the tuple is simply four ints, so it's easily represented using an int array with four elements.

Putting it all together, we get the following.

static Stream<int[]> build() {
    return IntStream.rangeClosed(240, 1280).boxed()
               .flatMap(w -> IntStream.rangeClosed(1, 10).map(m -> 2 * m).boxed()
                   .flatMap(m -> IntStream.rangeClosed(2, 100).boxed()
                       .flatMap(n -> IntStream.rangeClosed(240, 1280)
                                              .filter(g -> ((w - 2*m - n*g) % (n+1) == 0))
                                              .filter(g -> n*g+2*m <= w)
                                              .filter(g -> n*g <= w)
                                              .mapToObj(g -> new int[] { w, m, n, g }))));
}

This is clearly quite verbose compared to the original Haskell, but you can easily see where the Haskell constructs have ended up in the Java code. I believe this is correct, as it seems to generate the same output as the Haskell code.

Note that we are generating values using IntStream but we want the flatmap to give a stream of arrays (which are objects), whereas IntStream.flatMap returns an IntStream. Perhaps ideally there would be a flatMapToObj operation, but there isn't, so we must box the int value into an Integer object and then call Stream.flatMap it.

One could assign the stream pipeline to a variable of type Stream, but this wouldn't be very convenient, as Java streams can be used at most once. Since constructing such a stream is cheap (compared to evaluating it) it's reasonable to write a function build() that returns a freshly created stream, ready to be evaluated by the caller.

When the following Java code is run,

    System.out.println(build().count());
    System.out.println(build().findFirst().map(Arrays::toString).orElse("not found"));
    System.out.println(build().reduce((a, b) -> b).map(Arrays::toString).orElse("not found"));

the result is:

654559
[484, 2, 2, 240]
[1280, 20, 5, 248]

Running the following Haskell code (the definition of build is copied from the question)

build = [(w,m,n,g) | w <- [240..1280], m <- [2,4..20], n <- [2..100], g <- [240..1280],
                     ((w - 2*m - n*g) `mod` (n+1) == 0), n*g+2*m <= w, n*g <= w]

main = do
    print (length build)
    print (head build)
    print (last build)

gives the following output:

654559
(484,2,2,240)
(1280,20,5,248)

So the transliteration appears correct to my eye.

Times for the head (in Java, findFirst) and last (in Java, reduce((a, b) -> b)) operations were as follows: (updated using GHC 7.6.3 -O2)

       head     last
GHC      8s      36s
JDK      3s       9s

This at least shows that both systems provide laziness, as the computation is short-circuited after the first element is found, whereas finding the last element requires all to be computed.

Interestingly, in Haskell, calling all three of length, head, and last doesn't take any more time than just calling last (around 36s) presumably because of memoization. There's no memoization in Java, but of course you could explicitly store the results in an array or List and process that multiple times.

Overall, though, I was startled at how much faster the Java implementation is. I don't really understand Haskell performance, so I'll leave it to Haskell experts to comment on that. It's quite possible I've done something wrong, though mostly I just copied the function from the question into a file and compiled it using GHC.

My environment:

JDK 9, GHC 7.6.3 -O2, MacBook Pro mid 2014 2-core 3GHz Intel Core i7