Monday, March 04, 2013

An exercise in Refactoring - Playing around with Monoids and Endomorphisms

A language is powerful when it offers sufficient building blocks for library design and adequate syntactic sugar that helps build expressive syntax on top of the lower level APIs that the library publishes. In this post I will discuss an exercise in refactoring while trying to raise the level of abstraction of a modeling problem.

Consider the following modeling problem that I recently discussed in one of the Scala training sessions. It's simple but offers ample opportunities to explore how we can raise the level of abstraction in designing the solution model. We will start with an imperative solution and then incrementally work on raising the level of abstraction to make the final code functional and more composable.

A Problem of Transformation ..

The problem is to compute the salary of a person through composition of multiple salary components calculated based on some percentage of other components. It's a problem of applying repeated transformations to a pipeline of successive computations - hence it can be generalized as a case study in function composition. But with some constraints as we will see shortly.

Let's say that the salary of a person is computed as per the following algorithm :

  1. basic = the basic component of his salary
  2. allowances = 20% of basic
  3. bonus = 10% of (basic + allowances)
  4. tax = 30% of (basic + allowances + bonus)
  5. surcharge = 10% of (basic + allowances + bonus - tax)
Note that the computation process starts with a basic salary, computes successive components taking the input from the previous computation of the pipeline. But there's a catch though, which makes the problem a bit more interesting from the modleing perspective. Not all components of the salary are mandatory - of course the basic is mandatory. Hence the final components of the salary will be determined by a configuration object which can be like the following ..

// an item = true means the component should be activated in the computation
case class SalaryConfig(
  surcharge: Boolean    = true, 
  tax: Boolean          = true, 
  bonus: Boolean        = true,
  allowance: Boolean    = true 
)

So when we compute the salary we need to take care of this configuration object and activate the relevant components for calculation.

A Function defines a Transformation ..

Let's first translate the above components into separate Scala functions ..

// B = basic + 20%
val plusAllowance = (b: Double) => b * 1.2

// C = B + 10%
val plusBonus = (b: Double) => b * 1.1

// D = C - 30%
val plusTax = (b: Double) => 0.7 * b

// E = D - 10%
val plusSurcharge = (b: Double) => 0.9 * b

Note that every function computes the salary up to the stage which will be fed to the next component computation. So the final salary is really the chained composition of all of these functions in a specific order as determined by the above stated algorithm.

But we need to selectively activate and deactivate the components depending on the SalaryConfig passed. Here's the version that comes straight from the imperative mindset ..

The Imperative Solution ..

// no abstraction, imperative, using var
def computeSalary(sc: SalaryConfig, basic: Double) = {
  var salary = basic
  if (sc.allowance) salary = plusAllowance(salary)
  if (sc.bonus) salary = plusBonus(salary)
  if (sc.tax) salary = plusTax(salary)
  if (sc.surcharge) salary = plusSurcharge(salary)
  salary
}

Straight, imperative, mutating (using var) and finally rejected by our functional mindset.

Thinking in terms of Expressions and Composition ..

Think in terms of expressions (not statements) that compose. We have functions defined above that we could compose together and get the result. But, but .. the config, which we somehow need to incorporate as part of our composable expressions.

So direct composition of functions won't work because we need some conditional support to take care of the config. How else can we have a chain of functions to compose ?

Note that all of the above functions for computing the components are of type (Double => Double). Hmm .. this means they are endomorphisms, which are functions that have the same argument and return type - "endo" means "inside" and "morphism" means "transformation". So an endomorphism maps a type on to itself. Scalaz defines it as ..

sealed trait Endo[A] {
  /** The captured function. */
  def run: A => A
  //..
}

But the interesting part is that there's a monoid instance for Endo and the associative append operation of the monoid for Endo is function composition. That seems mouthful .. so let's dissect what we just said ..

As you all know, a monoid is defined as "a semigroup with an identity", i.e.

trait Monoid[A] {
  def append(m1: A, m2: A): A
  def zero: A
}

and append has to be associative.

Endo forms a monoid where zero is the identity endomorphism and append composes the underlying functions. Isn't that what we need ? Of course we need to figure out how to sneak in those conditionals ..

implicit def endoInstance[A]: Monoid[Endo[A]] = new Monoid[Endo[A]] {
  def append(f1: Endo[A], f2: => Endo[A]) = f1 compose f2
  def zero = Endo.idEndo
}

But we need to append the Endo only if the corresponding bit in SalaryConfig is true. Scala allows extending a class with custom methods and scalaz gives us the following as an extension method on Boolean ..

/**
 * Returns the given argument if this is `true`, otherwise, the zero element 
 * for the type of the given argument.
 */
final def ??[A](a: => A)(implicit z: Monoid[A]): A = b.valueOrZero(self)(a)

That's exactly what we need to have the following implementation of a functional computeSalary that uses monoids on Endomorphisms to compose our functions of computing the salary components ..

// compose using mappend of endomorphism
def computeSalary(sc: SalaryConfig, basic: Double) = {
  val e = 
    sc.surcharge ?? plusSurcharge.endo     |+|
    sc.tax ?? plusTax.endo                 |+|
    sc.bonus ?? plusBonus.endo             |+| 
    sc.allowance ?? plusAllowance.endo 
  e run basic
}

More Generalization - Abstracting over Types ..

We can generalize the solution further and abstract upon the type that represents the collection of component functions. In the above implementation we are picking each function individually and doing an append on the monoid. Instead we can abstract over a type constructor that allows us to fold the append operation over a collection of elements.

Foldable[] is an abstraction which allows its elements to be folded over. Scalaz defines instances of Foldable[] typeclass for List, Vector etc. so we don't care about the underlying type as long as it has an instance of Foldable[]. And Foldable[] has a method foldMap that makes a Monoid out of every element of the Foldable[] using a supplied function and then folds over the structure using the append function of the Monoid.

trait Foldable[F[_]]  { self =>
  def foldMap[A,B](fa: F[A])(f: A => B)(implicit F: Monoid[B]): B
  //..
}

In our example, f: A => B is the endo function and the append is the append of Endo which composes all the functions that form the Foldable[] structure. Here's the version using foldMap ..

def computeSalary(sc: SalaryConfig, basic: Double) = {
  val components = 
    List((sc.surcharge, plusSurcharge), 
         (sc.tax, plusTax), 
         (sc.bonus, plusBonus),
         (sc.allowance, plusAllowance)
    )
  val e = components.foldMap(e => e._1 ?? e._2.endo)
  e run basic
}

This is an exercise which discusses how to apply transformations on values when you need to model endomorphisms. Instead of thinking in terms of generic composition of functions, we exploited the types more, discovered that our tranformations are actually endomorphisms. And then applied the properties of endomorphism to model function composition as monoidal appends. The moment we modeled at a higher level of abstraction (endomorphism rather than native functions), we could use the zero element of the monoid as the composable null object in the sequence of function transformations.

In case you are interested I have the whole working example in my github repo.

10 comments:

Unknown said...

Great post! The endomorphism monoid is often handy. Here's a haskell version for fun:

https://gist.github.com/jhickner/5081100

Anonymous said...

Nice article!

I have a question as I'm new to Scala and I'm looking for a pattern similar to the one in the article, yet different.

I'd like to define a map that has a key as an Action, and a list of methods to be applied as a value.

I have this prototype, sorry for dumping this code here:

def doOne(user: String): List[String] = List("one" + "*" + user)

def doTwo(user: String): List[String] = List("two" + "*" + user)

def doThree(user: String): List[String] = List("three" + "*" + user)

def collectAll(funs: List[String => List[String]])(user: String): List[String] =
(List[String]() /: funs)((a, b) => a ::: b(user))

val actMap = Map(
"one" -> List(doOne _),
"one+two" -> List(doOne _, doTwo _)
)

def act(action: String, user: String): List[String] = {
collectAll(actMap(action))(user)
}

So I can do something like this with partially applied functions but they all take the same type and number of arguments. In my case I need to pass various args to functions, and I want it to happen without explicitly providing them. I can't think of a proper way of doing it. Method 'act' will be called by client which will provide args in some way. I'm suspecting that either continuations, closures or something else :) should allow me to do this.
I would appreciate to be pointed in a right direction. Thank you

Unknown said...

Dear Anonymous -

Your doOne, dotwo all seem to be String => String .. at least the implemented ones. Are they really String => String or String => List[String] ?

Unknown said...

Dear Anonymous -

Making the do* as vals will let u do away with the partial applications .. have a look at https://gist.github.com/debasishg/5097410 .. Let me know what u think.

Thanks.

Anonymous said...

Dear Debasish

Regarding the first question each do* function returns List[String]. Alternatively each function could be called as continuation if possible.

Anonymous said...

The best I could come up with is:

trait ActionMapper {
def id: Int
def active: Boolean

val doOne = (user: String) => List("one" + "*" + user)
val doTwo = (user: String) => List("two" + "*" + user + ":" + id)
val doThree = (user: String) => List("three" + "*" + user + ":" + active)

def collectAll(funs: List[String => List[String]])(user: String): List[String] =
(List[String]() /: funs)((a, b) => a ::: b(user))

val actMap = Map(
"one" -> List(doOne),
"one+two" -> List(doOne, doTwo),
"one+two+three" -> List(doOne, doTwo, doThree))

def act(action: String, user: String): List[String] = {
collectAll(actMap(action))(user)
}
}

object ActionExecutioner extends App with ActionMapper {
override val id = 321
override val active = false

println(act("one+two+three", "void"))
}

Using either val of def for do* functions.

I wonder if there is a more elegant way of doing it. The problem is that I have to implement/override both 'id' and 'active' in order to use the trait and thus I can't just do this:

object Fails extends ActionMapper {
act("one", "void")
}

although those args are not technically required for 'doOne'.

Alex

Anonymous said...

Dear Debasish

If you let me rephrase my question to make it more general...

What is a pattern for implementing a map class that maps a key (action) to a list of methods and how would a client go about calling those methods and passing arguments to them?

I greatly appreciate your help!

Unknown said...

You can try Kleisli >>= .. Will chalk out an implementation tonight ..

Anonymous said...

Dear Debasish,

Thank you for your advice. I read up on Kleisli. It looks very cool indeed and similar to what I'm trying to do. I'll try to rework my data representation to fit that pattern. I'll share my code if it will have anything interesting in it.

Once again big thanks,
Alex

xpmatteo said...

Hi Debasish,

you should not represent money with a Double. You are going to get inexact results. (See e.g. http://stackoverflow.com/questions/3730019/why-not-use-double-or-float-to-represent-currency)