Skip to content
Print

Function Currying in Scala

17
Mar
2008

As a hybrid-functional language, Scala supports many of the same techniques as languages like Haskell and LISP.  One of the least used and most misunderstood of these is that of function currying.  Furthermore, there are many articles talking about the various ways to use currying within languages like Ruby, Groovy and similar, but very few which actually discuss why it’s useful.  To that end, I present a quick run-down on how to curry methods in Scala, along with some idea of why you would want to.

Defining Curried Functions

Conceptually, currying is a fairly simple idea.  Wikipedia defines it as follows:

In computer science, currying, invented by Moses Schönfinkel and Gottlob Frege, is the technique of transforming a function that takes multiple arguments into a function that takes a single argument (the other arguments having been specified by the curry).

Mathematically,

f \colon (X \times Y) \to Z

\mbox{curry}(f) \colon X \to (Y \to Z)

What this is saying is that the currying process transforms a function of two parameters into a function of one parameter which returns a function of one parameter which itself returns the result.  In Scala, we can accomplish this like so:

def add(x:Int, y:Int) = x + y
 
add(1, 2)   // 3
add(7, 3)   // 10

And after currying:

def add(x:Int) = (y:Int) => x + y
 
add(1)(2)   // 3
add(7)(3)   // 10

In the first sample, the add method takes two parameters and returns the result of adding the two.  The second sample redefines the add method so that it takes only a single Int as a parameter and returns a functional (closure) as a result.  Our driver code then calls this functional, passing the second “parameter”.  This functional computes the value and returns the final result.

Of course, it’s not very apparent as to why this is a good idea.  All we’ve really accomplished is eliminate the second parameter and move it into another function.  This is a big deal in languages like Haskell which only allow a single parameter, but Scala doesn’t have this restriction.  For the moment, just assume with me that this is wonderful and profound as we move forward into a better implementation.

Our first example was nice, but it seems a little clumsy.  All we’ve done is add a ton of syntactic overhead to our add definition.  Fortunately, Scala has a nice syntax for defining curried functions which dates back to pure-functional languages like ML.  We can shorten our curried definition to something more like this:

def add(x:Int)(y:Int) = x + y
 
add(1)(2)   // 3
add(7)(3)   // 10

This is really just syntactic sugar, the compiler treats both definitions the same.

Applied to Existing Methods

Currying isn’t just limited to methods which you define.  Thanks to the power of a language with inner methods and closures, it is possible to define a method which takes a function of n parameters and converts it to a curried function of order n.  In fact, this function is already defined within the Function singleton in the scala package.  We can use it to curry the first version of our add method:

def add(x:Int, y:Int) = x + y
val addCurried = Function.curried(add _)
 
add(1, 2)   // 3
addCurried(1)(2)   // 3

That mysterious underscore within the curried method invocation is actually a bit of Scala syntax which tells the compiler to treat add as a function value, rather than a method to be invoked.  Scala refers to this as a “partially applied function”, though it doesn’t really meet the strictest definition.  More on this later.

It is interesting (and important) to note that the curried method is only overloaded for methods of up to arity (number of parameters) 5.  I suppose that only a maniac would want to define a curried version of a function of any higher arity, but it’s still odd to consider.

Function also provides utility methods which allow us to reverse the process.  For example, if we start with our second version of add, we may wish to generate a version which takes all parameters inline (in conventional fashion).  This can be done using the uncurried method:

def add(x:Int)(y:Int) = x + y
val addUncurried = Function.uncurried(add _)
 
add(3)(4)  // 7
addUncurried(3, 4)  // 7

As you can see, the process does invert quite nicely.  Notice that while this may appear to be dynamic programming (note), it’s actually quite static and valid from a compiler’s standpoint.  Effectively, addUncurried is a closure defined within the uncurried method.  Because we assign it to a val, we can call it anywhere in scope (anywhere we can access the addUncurried variable).  The compiler will type-check everything here, including the uncurried functional and its parameter types.

Partially Applied Functions

All of this is great, but it doesn’t answer the question: “why do we care?”  After all, when you look at the differences, it just seems that we’ve slightly altered the syntax for passing parameters.  This doesn’t even seem terribly mathematical (normally a trait of functional languages) since the notation for passing multiple variables is comma-delimited, not parentheses-separated.

It turns out that the best rationale for using currying has to do with general and specialized functions.  It would be nice to define a function for the general case, but allow users to specialize the function and then used the specialized version on different data sets.  Take the following code as an example:

def process[A](filter:A=>Boolean)(list:List[A]):List[A] = {
  lazy val recurse = process(filter) _
 
  list match {
    case head::tail => if (filter(head)) {
      head::recurse(tail)
    } else {
      recurse(tail)
    }
 
    case Nil => Nil
  }
}
 
val even = (a:Int) => a % 2 == 0
 
val numbersAsc = 1::2::3::4::5::Nil
val numbersDesc = 5::4::3::2::1::Nil
 
process(even)(numbersAsc)   // [2, 4]
process(even)(numbersDesc)  // [4, 2]

Aside from being a fair example of how imperative and functional programming blend well, this little ditty provides a convenient example with repeated code.  Astute observers will see that I could have easily done this using the List#filter method, but I wanted a curried function for an example.  Besides, I hadn’t even used the cons operator once on this blog and I figured it was about time to start…

The bit of code which is redundant is on the last two lines: the repeated invocation of process(even).  Not only is this redundant, but it’s somewhat inefficient.  To see why, we have to partially apply the curried function to look at the result type:

scala> process(even) _
res0: (List[Int]) => List[Int] = 

There again is our old friend the underscore.  Remember that it just tells the compiler to treat the suffixed value as a functional, rather than a method to be evaluated.  Thus it seems that invoking process(even) is perfectly valid in isolation.  We don’t have to specify the second parameter since there is none.  If the process method where not curried, there would be no way to do this (no way in most languages, we’ll see a way in Scala a little farther down).  The result type of this invocation is the functional which would be invoked next in the series (with the second set of parentheses).  Remember that a curried function is one which takes a parameter and returns another function which takes a parameter and does more processing.  We’re just accessing that intermediate function.

So if process(even) generates a functional, invoking it multiple times probably has some overhead.  To do so would be to create the intermediary functional twice.  Of course, the second problem is this is code-repeat,  something all good programmers cringe to see.  It turns out that we can solve both of these problems in one fell swoop:

//...
 
val even = (a:Int) => a % 2 == 0
val processEvens = process(even) _
 
val numbersAsc = 1::2::3::4::5::Nil
val numbersDesc = 5::4::3::2::1::Nil
 
processEvens(numbersAsc)   // [2, 4]
processEvens(numbersDesc)  // [4, 2]

Now we have a function processEvens of order 1 which specifically processes through an “even” filter.  We have created a specialized version of process by taking advantage of the way currying works.  This turns out to be a very powerful technique, and while I don’t have any non-trivial examples to share, I’m sure you can use your imagination.

Partials without Currying

It’s clear that partially applied functions can be very powerful, but they only seem to apply to a method which is already curried.  Of course, for a standard, arity n method we can use the curried method to convert, but this gets clumsy.  It would be nice if we could use the partially applied function technique on any method, even one which is not curried.  Enter underscore.

This little construct is probably the most powerful single character I’ve ever seen.  You can do so much with it in Scala, and yet it all seems to remain semantically consistent.  Scala allows us to use underscore within the invocation, partially applying the function by creating a new functional which takes the appropriate parameters.

def add(x:Int, y:Int, z:Int) = x + y + z
 
val addFive = add(5, _:Int, _:Int)
addFive(3, 1)    // 9

Here we have partially applied the add method, specializing on the value 5 for the first parameter.  addFive is actually a functional which takes two parameters of type Int and returns the result of passing the values of 5 and the two parameters in order to the add method.  This code is semantically equivalent to the following:

def add(x:Int, y:Int, z:Int) = x + y + z
 
val addFive = (a:Int, b:Int) => add(5, a, b)
addFive(3, 1)    // 9

The underscore just provides a convenient syntactic sugar for this.  The only unfortunate part is the fact that we must annotate the underscores with types.  If this were ML, Haskell or similar, the types of the underscores could easily be inferred and the annotations omitted.  It would be nice if Scala could do things like this, but I guess it can’t be entirely perfect.

Conclusion

Hopefully this provides a fair introduction to the useful world of method currying.  As you can see, currying is not just an academic construct we were forced to demonstrate on college exams, it’s a powerful technique with real-world applications.  By blending the functional and the object-oriented, Scala has managed to bring all the power of currying to the imperative world, a feat well worth utilizing on your next project.

Comments

  1. “Haskell which only allow a single parameter, but Scala doesn’t have this restriction”

    Not exactly true. Haskell allows tuple types as a parameter to a function, eg “(a, b) -> c”, which are no different from a Scala multi-parameter function. In fact there are two functions, curry and uncurry, which can convert freely between the two forms.

    Otherwise, great article, thanks!
    Neil

    Neil Bartlett Monday, March 17, 2008 at 2:14 am
  2. Hi Daniel,

    could you elaborate on the “process” function a little? Especially how the line

    lazy val recurse = process(filter)(tail)

    works and how Scala knows about the parameter “tail”.

    Thanks,

    David

    David Linsin Monday, March 17, 2008 at 6:27 am
  3. As you probably know, the type of placeholder parameters can be inferred if the target functional type is known. So if (Int, Int) => Int is the expected type, you could just pass in add(5, _, _) anonymously. Implying it from the way the parameters are used is harder, since the placeholder could also be used as

    val addFive = _ + _ + 5 // ¿que?

    If yours were treated as a special case I think the type could be inferred (?), but I find the anonymous use targeting a known functional type to be more common.

    n8 Monday, March 17, 2008 at 8:43 am
  4. Or, never mind, you can’t use placeholders like I was suggesting anyway. I’m not sure why the type isn’t implied there, seems like it could be. But, I think if I wanted a function like that I would use a def with regular parameters instead of a partially applied function anyway! ;)

    n8 Monday, March 17, 2008 at 9:02 am
  5. Elaboration: That was a typo. :-) It could theoretically work since recurse is not resolved until tail is available, but the compiler will not allow it. I’m correcting the article. As for the rest of the function…

    It’s basically just a block-standard functional list processing routine. You see this pattern (with pattern matching and cons) a lot in languages like ML. The routine runs through each element of the list, getting a reference to the current element, as well as the entire remainder. It then applies the filter() function to the current element. If the result is true, the current element is prepended to the result of recursively filtering on the remainder of the list. Otherwise, the current element is discarded and the the result is the recursive filter alone.

    @Neil
    Hmm, I knew that Haskell supported tuples but I didn’t know it had a nice syntax for passing them as parameters. Yet another reason why I need to study up on that language. :-)

    Daniel Spiewak Monday, March 17, 2008 at 9:02 am
  6. @n8
    I would tend to concur. The ability to define methods inner to other methods is one of my favorite features in Scala. I find myself habitually trying to write code that way in Java every time I have to switch back. :-)

    Daniel Spiewak Monday, March 17, 2008 at 9:07 am
  7. Never (ever) mind, it just needed parens:

    scala> val a = (_:Int) + (_:Int) + 5
    a: (Int, Int) => Int =

    or:

    scala> val a: ((Int, Int) => Int) = _ + _ + 5
    a: (Int, Int) => Int =

    So in the general case the placeholder’s type can not be implied. When it’s used a typed parameter, I don’t see why not. Maybe they just haven’t gotten around to it yet. Interesting stuff!

    n8 Monday, March 17, 2008 at 10:42 am
  8. I think most of the time this is just referred to as ‘currying’ rather than ‘function currying’. You can’t really curry a constant ;-) Otherwise, good post.

    Alex Blewitt Monday, March 17, 2008 at 5:09 pm
  9. Good point, Alex. Currying is the correct term. I tend to use “function currying” because it just sounds more clear. Not really to disambiguate, but to keep the terms associated for the sake of the uninitiated.

    Daniel Spiewak Monday, March 17, 2008 at 5:32 pm
  10. Good post!
    So I guess you can curry a Java method, which is nice.

    German B. Tuesday, March 18, 2008 at 5:36 am
  11. Unfortunately, you can’t *exactly* curry it in Java. At least, not Java 6 or earlier. If closures make it into Java 7, we’re going to see a lot more examples of this sort of thing for Java itself, not just derivative languages.

    Daniel Spiewak Tuesday, March 18, 2008 at 8:47 am
  12. Hi,

    i think the term “dynamic programming” is misused in this article. You probably mean something like dynamic typing but not http://en.wikipedia.org/wiki/Dynamic_programming.

    abu

    abulafia Tuesday, March 18, 2008 at 5:19 pm
  13. Yes, I am misusing the term “dynamic programming”. The problem is that there doesn’t seem to be a very good term to describe that particular concept. Dynamic typing is close, but insufficient. Meta-programming perhaps, but meta-programming is possible with entirely static constructs. We really need a new term which encompasses all of the modern techniques which go along with languages like Ruby and Groovy.

    Daniel Spiewak Tuesday, March 18, 2008 at 6:51 pm
  14. The type of the arguments of add5 can’t be inferred in general, because there might be overloaded add methods in scope with argument types (Int, Float, Float) and (Int, Boolean, String). Which one should add(5,_,_) resolve to?

    Florian Hars Thursday, March 20, 2008 at 12:33 am
  15. Very true, but it would still be nice to get the inference whenever possible.

    Daniel Spiewak Thursday, March 20, 2008 at 1:29 am
  16. Very cool post, you have a new reader :-)

    Landei Thursday, March 20, 2008 at 2:27 am
  17. Well a bit late to the game, but maybe i get an answer?

    As a Java-Programmer i am interested in Scala ’cause it presents all those functional advanced concepts in a very readable manner (unlike Lisp). Or let’s say in a form that’s much easier to grasp when used to Java.

    However i still fail to see what the difference in currying and using partially applied functions is (besides having to specify the types of the underscores): Both appear to return the exact same function signatures.

    You example with process, using partially applied functions:
    def process[A](filter:A=>Boolean,list:List[A]):List[A] = {
    lazy val recurse = process(filter, _:List[A])

    Everything else remains the same and it works as expected:
    scala> process(even,numbersAsc)
    res11: List[Int] = List(2, 4)

    scala> process(even,numbersDesc)
    res12: List[Int] = List(4, 2)

    So what is the reason for the special curryable form?

    Horst Makitta Thursday, April 1, 2010 at 2:29 pm
  18. Hi Horst!
    Yes both process methods have the same signatures. But the interesting bit is the processEvens function value where he combines a function (add) with the process method so that a new function value. And this only takes one parameter, you create a function with certain “default” behaviour. I think that’s it.

    Andreas S. Saturday, July 9, 2011 at 2:31 pm
  19. It’s correct hat strictly speaking Haskell functions can take only one parameter but I hope you understand that that’s more of an implementation detail, i.e. all Haskell functions are inherently curried which has the effect that you can work with function declarations as if they’re taking arbitrary amounts of arguments. No need for crappy workarounds like tuples if you want to pass more than one argument.

    Prelude> let add a b = a + b
    Prelude> let inc = add 1
    Prelude> add 2 3
    5
    Prelude> inc 3
    4

    and this works with arbitrary amounts of arguments. and of course this has also has whole-program type inference.

    Prelude> :t add
    add :: Num a => a -> a -> a

    Scala, although quite nice and a great choice among the JVM languages, doesn’t even come close to the awesomeness that is Haskell imo.

    anon Saturday, August 20, 2011 at 4:59 am
  20. Excellent article, I’ve understood what currying means reading this http://gleichmann.wordpress.com/2011/12/04/functional-scala-curried-functions-and-spicy-methods/

    but this helped me understand why it could be useful…

    opensas Monday, December 5, 2011 at 10:35 am
  21. Hi,

    Nice article. Perhaps a better application of currying is in writing your own control structures, as described in Programming in Scala, 2nd Edition, Chapter 9. Using currying you can write neat things like this, where we no longer have to worry about closing resources, because the control stucture does it for us:

    val f = new File(“c:\\temp\\someFile.txt”)

    //looks a little like a for comprehension. this works, because for functions taking ONE parameter, you can use braces or brackets to call it
    withPrintWriter(f){
    pw => pw.append(“now it is ” + new Date() + “\r\n”)
    }

    The function is defined as a curried function:

    def withPrintWriter(file: File)(op: PrintWriter => Unit) {
    val writer = new PrintWriter(file)
    try {
    op(writer)
    } finally {
    writer.close()
    }
    }

    Ant Kutschera Monday, January 9, 2012 at 1:21 pm

Post a Comment

Comments are automatically formatted. Markup are either stripped or will cause large blocks of text to be eaten, depending on the phase of the moon. Code snippets should be wrapped in <pre>...</pre> tags. Indentation within pre tags will be preserved, and most instances of "<" and ">" will work without a problem.

Please note that first-time commenters are moderated, so don't panic if your comment doesn't appear immediately.

*
*