Templates and Strategies – functional approach in Java

The problem, in general

Sometimes I come across large bodies of code which do almost the same. They have a few differences though: a complex conditional here, some logging there, invoking another void method there. Breaking things up into smaller methods results in clean code methods with many parameters, some of them may be null. On the other hand, we could extract the orthogonal chunks of code which eventually do something. FP-ish constructs like Strategies and Templates come to our rescue. Or not, we’ll see.

Explaining Functional Programming

Once when I was explaining the rise of functional programming to my co-workers, one of them asked me: “Is immutability a feature?” – It’s funny when smart people ask stupid questions.

There are many definitions of functional programming languages. One could say they have no mutable data. One could say that they treat functions as first-class citizens. None of these things are features. All of them are available in C++. However, a functional programming language provides a concise and efficient way to deal with immutable data and function literals. Now, that’s a feature. Emulating them in other languages is a non-trivial task. Say, for instance, the guava page that explains functional idioms explains the caveats first.

The problem, in particular

To model the original problem I choose list-reducing: we have a list of values and we want to do something with them until we have a single value. E.g. we could add every element of the list. Or we could multiply each element with 3 and multiply the elements with each other.

This problem was an example in the progfun course. Effective Java item #25 mentions it too. Of course there is a python function implementing it. I chose this problem because you can implement in many different ways – each of them shows a prototype of our original problem: too much code with many little differences.

This is a concrete example in java:

package com.example;

import java.util.Arrays;
import java.util.List;

public class ReduceListConcrete {

	public static void main(String[] args) {
		List exampleInput = Arrays.asList(new Integer[]{1, 2, 3, 4, 5});
		System.out.println(reduceConcrete(exampleInput));
	}

	private static Integer reduceConcrete(List input) {
		int result = 0;
		for (Integer item : input) {
			result += item * 3;
		}
		return result;
	}
}

Here is a concrete example in scala:

package com.example

object ReduceListConcrete {

  def main(args: Array[String]): Unit = {
	val exampleSeq = 1 to 5
	println(reduceConcrete(exampleSeq))
  }

  def reduceConcrete(input: Seq[Int]): Int = {
    input.map(_ * 3).sum
  }
}

Disclaimer: I didn’t use any unit tests because I didn’t want to maintain these snippets in the long run. I’m using them as simplistic examples.

Both of the examples multiply each item with 3 and then sum the full list. The scala code is a functional solution. On the other hand, the java code uses a for-loop and mutable state. It isn’t that bad, as scala foldleft implementation too uses mutable state.

Instead of summing numbers multiplied with three, we could also generate a hash-code with some serious magic that involves relative primes. We could use it to find the least common multiple for 3 or more numbers. We could do many other things that boil down to this simple example. Let’s see how we could re-implement it!

Naïve implementations

This is a naïve implementation in scala:

package com.example

object ReduceListNaive {

  def main(args: Array[String]): Unit = {
	val exampleSeq = 1 to 5

    val reducedSum = reduceNaive(exampleSeq, 0, _+_, _*3)
    println(reducedSum)

    val reducedProd = reduceNaive(exampleSeq, 1, _*_, _*3)
    println(reducedProd)
  }

  def reduceNaive(input: Seq[Int], nillElement: Int, reducer: (Int, Int) => Int, mapper: Int => Int): Int = {
    def reduceNaiveInner(acc: Int, input: Seq[Int]): Int = {
      if (input.isEmpty) {
        acc
      } else {
        val x = input.head
        val mapped = mapper(x)
        val nextAcc = reducer(acc, mapped)
        reduceNaiveInner(nextAcc, input.tail)
      }
    }

    reduceNaiveInner(nillElement, input)
  }

}

This isn’t really why functional programming is going to rise: this method has many parameters, sometimes it’s hard to tell which is which. It’s unclear why we start the reducing with the nillElement. It looks a bit encrypted but at least it works.

This is how to do the same in java:

package com.example;

import java.util.Arrays;
import java.util.List;

public class ReduceListStrategies {

	public static void main(String[] args) {

		List exampleInput = Arrays.asList(new Integer[]{1, 2, 3, 4, 5});

		Mapper multipleBy3 = new Mapper() {
			@Override
			public Integer map(Integer item) {
				return item * 3;
			}
		};

		Reducer sum = new Reducer() {
			@Override
			public Integer reduce(Integer a, Integer b) {
				return a + b;
			}
		};

		Reducer prod = new Reducer() {
			@Override
			public Integer reduce(Integer a, Integer b) {
				return a * b;
			}
		};

		System.out.println(reduceWithStrategies(exampleInput, 0, multipleBy3, sum));
		System.out.println(reduceWithStrategies(exampleInput, 1, multipleBy3, prod));
	}

	private static Integer reduceWithStrategies(List input, Integer initial, Mapper mapper, Reducer reducer) {
		Integer result = initial;
		for (Integer item : input) {
			Integer mapped = mapper.map(item);
			result = reducer.reduce(result, mapped);
		}
		return result;
	}

	private static interface Mapper {
		public Integer map(Integer item);
	}

	private static interface Reducer {
		public Integer reduce(Integer a, Integer b);
	}
}

It’s even less readable. It uses interfaces to define function types; then uses anonymous inner classes to implement them. Clearly, not elegant. Instead of cleaning things up, it encrypts the code. It’s also the first solution I came up with.

Examples with foldLeft and foldRight

This other snippet shows how to implement the task with map and fold methods:

package com.example

object ReduceListMapAndFold {

  def main(args: Array[String]): Unit = {
	val exampleSeq = 1 to 5

    val leftFolded = exampleSeq.map(_*3).foldLeft(0)(_+_)
    val rightFolded = exampleSeq.map(_*3).foldRight(0)((x, y) => x + y)
    val leftFoldedProd = exampleSeq.map(x => x*3).foldLeft(1)(_*_)
    val rightFoldedProd = exampleSeq.map(_*3).foldRight(1)(_*_)

    println(leftFolded)
    println(rightFolded)
    println(leftFoldedProd)
    println(rightFoldedProd)
  }
}

The map method applies its parameter function to each element of the list and returns a new list. I.e. if you take the list [1, 2, 3] and map it with a function that multiplies each element with 3 then you’ll get [3, 6, 9]. Then, foldLeft/foldRight (they are the same for associative operation) reduces the list: they start with the initial element (0 for sum and 1 for prod), then apply a method with two parameters: one is the accumulated result, the other is the next element in the list.

I’m showing examples for both syntaxes of the anonymous functions: the arrow and the underscore syntax. The arrow syntax is the same that we used for functions in math class. The underscore syntax is a wildcard-magic that I don’t fully understand but I can get it right most of the time.

Actually, the fold methods are so powerful that we can implement the thing using the fold methods only:

package com.example

object ReduceListFoldOnly {

  def main(args: Array[String]): Unit = {
	val exampleSeq = 1 to 5

    val leftFoldedNoMap = exampleSeq.foldLeft(0)((x, y) => (x + (y * 3)))
    val rightFoldedProdNoMap = exampleSeq.foldRight(1)(_*_*3)
    println(leftFoldedNoMap)
    println(rightFoldedProdNoMap)
  }

}

Errr… it’s unreadable again: the function parameter is unnecessarily complex. It’s unclear which parameter to multiply with. That’s a good reason for not doing this anymore.

Doing it in Java

We already saw that using a strategy object for each method results hard-to-read code. With template methods we can write more concise code:

package com.example;

import java.util.Arrays;
import java.util.List;

public class ReduceListInlineTemplate {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		List exampleInput = Arrays.asList(new Integer[]{1, 2, 3, 4, 5});

		ReducerTemplate mulBy3AndSum = new ReducerTemplate() {
			@Override
			protected Integer getInitialElement() {
				return 0;
			}
			@Override
			protected Integer reduceTwoItems(Integer a, Integer b) {
				return a + b;
			}
			@Override
			protected Integer map(Integer item) {
				return item * 3;
			}
		};
		System.out.println(mulBy3AndSum.reduce(exampleInput));

		ReducerTemplate mulBy3AndProd = new ReducerTemplate() {
			@Override
			protected Integer getInitialElement() {
				return 1;
			}
			@Override
			protected Integer reduceTwoItems(Integer a, Integer b) {
				return a * b;
			}
			@Override
			protected Integer map(Integer item) {
				return item * 3;
			}
		};
		System.out.println(mulBy3AndProd.reduce(exampleInput));
	}

	private static abstract class ReducerTemplate {
		public Integer reduce(List input) {
			Integer result = getInitialElement();
			for (Integer item : input) {
				Integer mapped = map(item);
				result = reduceTwoItems(result, mapped);
			}
			return result;
		}

		protected abstract Integer getInitialElement();

		protected abstract Integer reduceTwoItems(Integer a, Integer b);

		protected abstract Integer map(Integer item);
	}
}

The abstract ReducerTemplate defines 3 hook methods. You can see two direct concrete subclasses: they nicely group all the different behaviors. This is something that could work in an enterprise. On the downside, some hooks have to be repeatedly re-implemented.

To keep ourselves from re-implementing the same hooks again and again, we can create several layers of abstract subclasses which implement one hook at a time. However, this creates complicated and brittle taxonomies. Here it is:

package com.example;

import java.util.Arrays;
import java.util.List;

public class ReduceListPredefTemplates {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		List exampleInput = Arrays.asList(new Integer[]{1, 2, 3, 4, 5});

		MultiplyBy3AndSum m3as = new MultiplyBy3AndSum();
		System.out.println(m3as.reduce(exampleInput));

		MultiplyBy3AndProd m3ap = new MultiplyBy3AndProd();
		System.out.println(m3ap.reduce(exampleInput));
	}
	private static abstract class ReducerTemplate {
		public Integer reduce(List input) {
			Integer result = getInitialElement();
			for (Integer item : input) {
				Integer mapped = map(item);
				result = reduceTwoItems(result, mapped);
			}
			return result;
		}

		protected abstract Integer getInitialElement();

		protected abstract Integer reduceTwoItems(Integer a, Integer b);

		protected abstract Integer map(Integer item);
	}

	private static abstract class SumTemplate extends ReducerTemplate {
		@Override
		protected Integer getInitialElement() {
			return 0;
		}
		@Override
		protected Integer reduceTwoItems(Integer a, Integer b) {
			return a + b;
		}
	}

	private static abstract class ProdTemplate extends ReducerTemplate {
		@Override
		protected Integer getInitialElement() {
			return 1;
		}
		@Override
		protected Integer reduceTwoItems(Integer a, Integer b) {
			return a * b;
		}
	}

	private static class MultiplyBy3AndSum extends SumTemplate {

		@Override
		protected Integer map(Integer item) {
			return 3 * item;
		}
	}

	private static class MultiplyBy3AndProd extends ProdTemplate {

		@Override
		protected Integer map(Integer item) {
			return 3 * item;
		}
	}

}

To enhance performance we could use singleton items of the templates.

package com.example;

import java.util.Arrays;
import java.util.List;

public class ReduceListSingletonTemplates {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		List exampleInput = Arrays.asList(new Integer[]{1, 2, 3, 4, 5});
		System.out.println(MultiplyBy3AndSum.INSTANCE.reduce(exampleInput));
		System.out.println(MultiplyBy3AndProd.INSTANCE.reduce(exampleInput));
	}
	private static abstract class ReducerTemplate {
		public Integer reduce(List input) {
			Integer result = getInitialElement();
			for (Integer item : input) {
				Integer mapped = map(item);
				result = reduceTwoItems(result, mapped);
			}
			return result;
		}

		protected abstract Integer getInitialElement();

		protected abstract Integer reduceTwoItems(Integer a, Integer b);

		protected abstract Integer map(Integer item);
	}

	private static abstract class SumTemplate extends ReducerTemplate {
		@Override
		protected Integer getInitialElement() {
			return 0;
		}
		@Override
		protected Integer reduceTwoItems(Integer a, Integer b) {
			return a + b;
		}
	}

	private static abstract class ProdTemplate extends ReducerTemplate {
		@Override
		protected Integer getInitialElement() {
			return 1;
		}
		@Override
		protected Integer reduceTwoItems(Integer a, Integer b) {
			return a * b;
		}
	}

	private static class MultiplyBy3AndSum extends SumTemplate {

		private static final MultiplyBy3AndSum INSTANCE = new MultiplyBy3AndSum();

		@Override
		protected Integer map(Integer item) {
			return 3 * item;
		}
	}

	private static class MultiplyBy3AndProd extends ProdTemplate {

		private static final MultiplyBy3AndProd INSTANCE = new MultiplyBy3AndProd();

		@Override
		protected Integer map(Integer item) {
			return 3 * item;
		}
	}

}

Doesn’t repeat itself, performs well, but ugly, isn’t it? It has too many smart solutions. And we didn’t use the lazy-loading holder idiom so far. (We won’t.)

The Spring style

Fortunately we aren’t the first folks doing serious pattern magic. The Spring community combined the Template and the Strategy patterns to eliminate the JDBC and the JMS boilerplate code. This is how to do the same with list-reducing:

package com.example;

import java.util.Arrays;
import java.util.List;

public class ReduceListTemplateAndStrategy {

	public static void main(String[] args) {
		List exampleInput = Arrays.asList(new Integer[]{1, 2, 3, 4, 5});

		Mapper mulWith3 = new Mapper() {
			@Override
			public Integer map(Integer val) {
				return 3 * val;
			}
		};
		SumTemplate sum = new SumTemplate();
		System.out.println(sum.reduce(exampleInput, mulWith3));

		ProdTemplate prod = new ProdTemplate();
		System.out.println(prod.reduce(exampleInput, mulWith3));
	}

	private static interface Mapper {
		public Integer map(Integer val);
	}

	private static abstract class ReducerTemplate {
		public Integer reduce(List input, Mapper mapper) {
			Integer result = getInitialElement();
			for (Integer item : input) {
				Integer mapped = mapper.map(item);
				result = reduceTwoItems(result, mapped);
			}
			return result;
		}

		protected abstract Integer getInitialElement();

		protected abstract Integer reduceTwoItems(Integer a, Integer b);
	}

	private static class SumTemplate extends ReducerTemplate {
		@Override
		protected Integer getInitialElement() {
			return 0;
		}
		@Override
		protected Integer reduceTwoItems(Integer a, Integer b) {
			return a + b;
		}
	}

	private static class ProdTemplate extends ReducerTemplate {
		@Override
		protected Integer getInitialElement() {
			return 1;
		}
		@Override
		protected Integer reduceTwoItems(Integer a, Integer b) {
			return a * b;
		}
	}

}

This is the most concise and DRY java code we can get.

So, why did we do all this magic?

On the beginning of this article we imagined a very ugly spaghetti code. So, how can we get rid of its duplications? There is more than one way to do it. Functional approach is certainly one of them. Just be careful to keep the code readable.

An exercise for the reader

One could use the Decorator pattern too. Just for the heck of it, one could even use aspects. The map function is a good candidate to utilize them.

If you think I skipped a useful way of doing it or you just know something smarter, please let me know.

Advertisements

About tamasrev

A software developer, specialized in Java, addressing himself as generalist. A proud daddy.
This entry was posted in Uncategorized and tagged , , , . Bookmark the permalink.

One Response to Templates and Strategies – functional approach in Java

  1. Pingback: Learning Python | tamasrev

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s