Circular programming in Java with cyclops

Circular programming allows algorithms that traditionally require multiple traversals of data to be implemented in a single pass. I came across an interesting blog on the concept in Haskell, and wondered if it were possible to replicate this technique in Java. The technique involves defining an algorithm lazily such that the result of the algorithm can be referenced during the execution of the algorithm itself.

Haskell doesn’t have iterative loops so circular programming involves recursive programming, Java on the other hand doesn’t support Tail Recursion — but as iteration and recursion are functionally equivalent we will attempt to implement circular programming techniques in Java iteratively. In this article we will make use of 2 lazy datastructures from cyclops-react ListX a lazy extended List and Eval which represents a value calculated lazily.

Photo by Štefan Štefančík on Unsplash

Minimum values from a List

A very simple algorithm would be to change all values in a List to the minimum value present in that list. Implementing this in imperative Java would be very straightforward, with circular programming it is more challenging, but possible.

The interface of our minimum method should look something like the signature below, implying we will accept a List and return a List with all elements converted to the minimum.

public ListX<Integer> minumum(ListX<Integer> ints)

We can implement the algorithm by performing a fold (or reduce operation) across the List. We will have to do 2 things as we go.

1. Calculate the minimum value
2. Rebuild the List with a reference to the minimum value (we need to return a List after all)

A handy typed Object that can store two values for us is a Tuple2. The result of our fold operation should look something like this (Integer: minimum, List[Integer] : minimums)

Tuple2<Integer,ListX<Integer>> data

We are going to lazily calculate the minimum value, and if we make use of cyclops-react’s Eval type to do this our type signature would become (Integer: minimum, List[Eval[Integer]] : list of lazy refs to minimum)

Tuple2<Integer,ListX<Eval<Integer>>> data

We can reference the minimum value lazily, as the first element in the data Tuple as follows (using v1 to access the first element of the Tuple2)

Eval<Integer> minimum = Eval.later(()->data.v1);

The next piece of the puzzle is to replace every element in the List with the reference to our minimum value and to calculate the minimum value itself. Separately we could create a list with reference to our lazy minimum

ListX<Eval<Integer>> minRef = ints.map(i->minimum);

We could use foldLeft to calculate what the minimum is

int minValue = ints.foldLeft(Integer.MAX_VALUE,(a,b) a<b?a:b);

This involves two passes over our List data, something we can improve on at a cost of increased code complexity. We have to make use of a Tuple2 to capture both the accumulated minimum value and to rebuild the list containing a lazy reference to the minimum value.

Tuple2<Integer,ListX<Eval<Integer>>>

So our map operation should map the List into this format

ListX<Tuple2<Integer,ListX<Eval<Integer>>>>

which can be done by capturing the current value and the lazy reference to the minimum value

ints.map(i -> Tuple.tuple(i, minimum))

We can avoid defining a variable with the full type signature at this point, and move on the fold operation. When folding over the list this we need to calculate the current accumulated minimum value (using the first parameter on our tuple t.v1) and to rebuild the list appending a lazy reference to the minimum each time inside our second tuple parameter (t.v2)

.foldLeft(Tuple.tuple(Integer.MAX_VALUE, ListX.empty()), 
                     (a, b) ->  a.v1 < b.v1 ? 
                                      tuple(a.v1, 
                                            a.v2.plus(minimum)) : 
                                           tuple(b.v1,  
                                           a.v2.plus(minimum)));

Putting the calls together we get this monstrosity / code :-

import static cyclops.collections.mutable.ListX.empty;
import static org.jooq.lambda.tuple.Tuple.tuple;
data = ints.map(i -> tuple(i, minimum))
           .foldLeft(tuple(MAX_VALUE, empty()), 
                     (a, b) ->  a.v1 < b.v1 ? 
                                      tuple(a.v1, 
                                            a.v2.plus(minimum)) : 
                                           tuple(b.v1,  
                                           a.v2.plus(minimum)));

Pretty horrendous in it’s complexity but we are able to define a List that lazily refers to the result of an operation on that List.

The last step is to return the List of mimimums, to do this we can lazily map data, extracting the minimum result from the lazy Eval.

return data.v2.map(Eval::get);

Average values for a List

We can use very similar code to calculate the average values in a List. When we traverse the List if we capture the total of the values so far as well as the number of values we can use that to calculate the average.

Rather than make use of 2 generic Tuple2 instances, which would seriously complicate our type signatures, this time we can create a simple value class to capture the total and length — using Lombok this would look like

@Value
public class TotalAndLength {
    final int total;
    final int length;
};

The method signature for data (the result of our fold operation) would have TotalAndLength as the first parameter in the tuple

Tuple2<TotalAndLength,ListX<Eval<Double>>> data

And our lazy averaging calculation would become

Eval<Double> average = Eval.later(()->(double)data[0].v1.total / data[0].v1.length);

The rest of the algorithm is very similar as for calculating the minimum value. Our fold operation even becomes slightly simpler.

Photo by Samuel Zeller on Unsplash

Reducing each value in a List by the average

We can further extend our averaging example to reduce the value of each entry in the list by the average. In our foldLeft code where we rebuild the List adding a reference to the Lazy average reference

//list.plus(average)
acc.v2.plus(average)

we should modify the reference such that it substracts that value from the Lists current value

//list.plus(average.map(avgValue->current.total-avgValue))
acc.v2.plus(average.map(avgValue->current.v1.total-avgValue))

This leaves our code looking like this