Salmon Run: Functional Chain of Responsibility implementation in Scala

Sunday, June 09, 2013

Functional Chain of Responsibility implementation in Scala

The Chain of Responsibility pattern can be very useful for building configuration driven pipeline style applications. We have made extensive use of this in both our search and indexing pipelines, and because we are a Java shop, our implementation looks a lot like this.

Recently, I was trying to port some of this stuff over to Scala. Now the Scala style favors immutability, which goes kind of counter to the Chain of Responsibility idea, since each command object in the pipeline gets a whack at the processing object passing through it, potentially mutating it.

One way to work with immutable objects is to think about this in a recursive way. Consider a pipeline of command objects (or Functions, since Functions are a first class concept in Scala) fs = [f1, f2, f3, ...], which successively operate on a processing object x. In pseudo-code, the Java approach would look like this:

1
2
3

x = initial_value
    for f in fs:
      x = f(x)

which can be rewritten thus:

x = initial_value
    x = f1(x)
    x = f2(x)
    x = f3(x)

which is the same as this:

1 2	x = initial_value x = f3(f2(f1(x)))

And this can now easily be rewritten recursively by successively applying the head of the function list to the object until the list is empty. The Scala code snippet below shows both the imperative and the functional approach.

import scala.annotation.tailrec

object CoRExample extends App {

  def f1 = (x: Int) => x + 1
  def f2 = (x: Int) => x + 2
  def f3 = (x: Int) => x * 2
  
  val fs = List(f1, f2, f3)
  
  // classical approach
  var x1 = 42
  for (f <- fs) {
    x1 = f(x1)    
  }
  Console.println("x1 = " + x1)
  
  // functional approach
  val x2 = transform(42, fs)
  Console.println("x2 = " + x2)
  
  @tailrec
  def transform(x: Int, fs: List[(Int) => Int]): Int = {
    if (fs.isEmpty) x
    else transform(fs.head(x), fs.tail)
  }
}

This was a bit of an epiphany for me, but apparently this is a fairly common transform. This blog post by Yuriy Polyulya shows some other ways of implementing the Chain of Responsibility Pattern in Scala.