# Life, Programming, Everything

When I find something interesting and new, I post it here - that's mostly programming, of course, not everything.

## Monday, October 06, 2008

### Unlimited Cartesian Product in Java - part 2

(This is the second part, see part 1).

Here is the code that implements Cartesian product in Java. The implementation amounts to providing the following methods of class Cartesian:

``     public static <X, XS extends Iterable<X>>        Iterable<Iterable<X>> product(final XS... xss) {      return product(Arrays.asList(xss));    }    public static <X, XS extends Iterable<X>>        Iterable<Iterable<X>> product(final Iterable<XS> xss) {      return new Cartesian<X, XS>().calculateProduct(xss);    }``

So we could write code like this:

``  Iterable<Iterable<Integer>> theProduct =       Cartesian.product(Arrays.asList(          Arrays.asList(1, 2, 3),           Arrays.asList(4, 5, 6)));    assertEquals(9, Set(actual).size());``

and like this:

``  Iterable<Iterable<Integer>> theProduct =     Cartesian.product(        Arrays.asList(1, 2, 3),         Arrays.asList(4, 5, 6));``

Note that we could not use `Iterable<Iterable<X>>`, since, imagine, in this case we could not even build a product of `Set<Set<X>>`.

How do we `calculateProduct`? The idea is that we define it by recursion. If we have `X0, X1,..., Xn`, we define `product(X0, X1,..., Xn)` as `X0 x product(X1, X1,..., Xn)`; and if the sequence is actually empty, we return a singleton,
``new ArrayList<Iterable>() {{            add(Collections.EMPTY_LIST);          }};``
(I use crazybob's contraption to build the singleton).

``  private Iterable<Iterable<X>>      calculateProduct(final Iterable<XS> xss) {    if (xss.iterator().hasNext()) {      Pair<XS, Iterable<XS>> pair = split(xss);      XS head = pair.x();      Iterable<XS> tail = pair.y();      return appendComponentToProduct(head, calculateProduct(tail));    } else {      return new ArrayList<Iterable<X>>() {{        add(Collections.EMPTY_LIST);      }};    }  }``

Here I use two methods, `split` and `appendComponentToProduct`. The first one is obvious (okay, it's an exercise if you are a beginner); the second one is here. See what it does: we have a component, `X0`, say,
`[1, 2, 3]`
, and a product of previous components `X1 x ... x Xn`, which is an iterable of iterables, e.g. [[4, 5], [5, 6]]; we need to append elements of `X0` to all elements of the partial product. That appendage function is called `consWith`: it takes an x and appends it to all partial product elements. We apply this function to the whole `X0`; what we receive has to be flattened to produce a list of tuples `[x0, x1, ..., xn]`

``  private Iterable<Iterable<X>>      appendComponentToProduct(        XS component,         Iterable<Iterable<X>> partialProduct) {      // E.g. [1, 2, 3], [[4, 6], [5, 6]] ->       // [[[1, 4, 6], [1, 5, 6]], [[2, 4, 6], [2, 5, 6]], [[3, 4, 6], [3, 5, 6]]] ->      // [[1, 4, 6], [1, 5, 6], [2, 4, 6], [2, 5, 6], [3, 4, 6], [3, 5, 6]]       return flatten(consWith(partialProduct).map(component));``

Flattening is, again, a trivial exercise; let's take a look at our `consWith`. It is a method that returns a function (which we apply to the component `X0`:

``    public <ElementOfProduct extends Iterable<X>>        Function<X, Iterable<Iterable<X>>>        consWith(final Iterable<ElementOfProduct> pxs) {      return new Function<X, Iterable<Iterable<X>>>() {        // takes an x, returns a function appending x to sequences        public Iterable<Iterable<X>> apply(final X x) {          // Takes a sequence [x1, x2, ...], returns [x, x1, x2, ...]          return new Function<ElementOfProduct, Iterable<X>>() {            public Iterable<X> apply(ElementOfProduct y) {              return concat(Arrays.asList(x), y);            }          }.map(pxs);        }      };    }``

A little bit dizzy? It's okay. We have arrived to the summit.

This is Higher Order Java!