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 :

- basic = the basic component of his salary
- allowances = 20% of basic
- bonus = 10% of (basic + allowances)
- tax = 30% of (basic + allowances + bonus)
- surcharge = 10% of (basic + allowances + bonus - tax)

*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:

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

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

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

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] ?

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.

Dear Debasish

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

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

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!

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

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

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)

Post a Comment