Scala currying without lab rats

What is it?

In normal function evaluation, you supply all of the arguments of a function and get back a result. Currying is a technique for specializing a function by providing some of the arguments, in which case you get back a function with fewer arguments. This technique is widely used in functional programming, and is named after logician and mathematician Haskell Curry (who is also honored by a programming language using his first name).

As the well-known joke goes, “I’m glad we don’t have to call it Schoenfinkeling!”

A practical example

Some US states compute sales tax by a scheme similar to the following: there are two rates applied, one to the entire taxable value, the other to some part of the value up to a limit. (And it obviously gets more complicated than that, but this is enough real-world complexity for our example.)

For example, here are the sales tax policies for three hypothetical states.

Abbr. State City Tax computation
TF Terrafirma n/a 2% of the entire value
TC Terracotta n/a 6% on the first $1500
CF Confusion Gotham 5% on the entire value plus 4.5% on the first $1000
CF Confusion Ocean City 5% on the entire value plus 3% on the first $1000
CF Confusion Hometown 5% on the entire value plus 1.5% on the first $1000

Without currying

With a helper to compute a rounded percentage…

    def pct(rate: Double, amt: Long) =
(rate * amt / 100.0D + 0.5D).toLong

… we could fit all these cases into the single method below. (To keep things simple, we’re representing money amounts as whole cents.)

    def tax(rateA: Double, limit: Long, rateB: Double, amt: Long) =
pct (rateA, amt) + pct (rateB, limit min amt)

With that general method in hand, we can define functions for the various locations.

    def taxTF         (amt: Long) = tax(2.0D,      0, 0.0D, amt)
def taxTC         (amt: Long) = tax(0.0D, 150000, 6.0D, amt)
def taxGothamCF   (amt: Long) = tax(5.0D, 100000, 4.5D, amt)
def taxOceanCityCF(amt: Long) = tax(5.0D, 100000, 3.0D, amt)
def taxHometownCF (amt: Long) = tax(5.0D, 100000, 1.5D, amt)

The significant changes are hidden in the mass of boilerplate code, which means a large amount of redundant typing (and reading). Let’s look a the difference when we revise the implementation to use currying.

Now with a dash of curry

First, we replace the method above with a curried function. (The extra line-breaks aren’t significant; they’re just fitting the slightly longer line into a narrow blog page layout.)

    def tax =
(rateA: Double) =>
(limit: Long  ) =>
(rateB: Double) =>
(amt:   Long  ) =>
pct (rateA, amt) + pct (rateB, limit min amt)

The first improvement shows up when we define the sales tax functions for Terrafirma and Terracotta:

    def taxTF = tax( 2.0D)(     0)(0.0D)
def taxTC = tax( 0.0D)(150000)(6.0D)

Currying lets us define the specialized functions directly and simply, without the need for all the boilerplate. Providing only the first three arguments to tax, we get back functions that take the one remaining argument, the amount of the sale.

It gets even nicer when we start to deal with the great state of Confusion. We begin by defining a state-level function…

    def taxCF = tax( 5.0D)(100000)

… which we then use in the definitions of the individual locales.

    def taxGothamCF    = taxCF( 4.5D)
def taxOceanCityCF = taxCF( 3.5D)
def taxHomeTownCF  = taxCF( 1.0D)

Could we do this without currying? Of course! But the point is that the curried version eliminates almost all of the typing except for the part that’s significant: the arguments that change for each specialized version. By supporting currying and the use of functions as first-class values (e.g., as arguments of other functions, as returned values from functions, etc.), Scala and other functional languages encourage us to think of composing programs as a much finer-grained level.

As a small example, we can create a function such as:

    def report(taxf: (Long => Long), amts: List[Long]) = {
println("Tax on " + amts + " is " + taxf(amts.foldRight(0L)(_ + _)))
}

Given a list of item prices…

    val items = List[Long](20000, 40000, 60000, 80000)

…we can apply shotItemsTax with a defined tax function:

    report(taxHometownCF, items)

We can also apply it to an-inline function literal based on our curried tax functions:

    report(taxCF(0.5D), items)

And that reflects the larger goal of making the definition, customization, and application of functions as painless as possible.

What about those lab rats?

There was a recent discussion on Artima of an article on currying. The original author used illustrations based on simple numerical calculations, something I’ve done in many conversations or classes.

My rationale has always been this: I want to illustrate a technique without requiring that the reader/audience spend time learning the problem domain. Presumably anyone who would read an article about a programming technique would already know arithmetic, and therefore could concentrate on the technique instead of the example. Biased by my own background, I tend to think of the Euclidean algorithm, factorials, and Fibonacci numbers as the standard lab rats of computing. But I’ve slowly begun to appreciate that people whose learning/thinking style is more inductive than deductive may prefer concrete examples that resemble their day-to-day programming tasks.

Advertisements
Trackbacks are closed, but you can post a comment.

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

%d bloggers like this: