Implementing a higher order function that performs currying in scala

Question

One of my colleagues asked me a question:

To implement HOF (a higher-order function) that performs currying, the signature of your function is as follows:

def curry[A,B,C](f:(A,B) => C) : A => B => C 

Similarly, implement a function that performs the following actions:

 def uncurry[A,B,C](f:A => B => C): (A,B) => C 

I understand that if you use a function that takes several parameters, you can repeatedly apply this function to each of the parameters until you get the result.

So, something along the lines f:(A,B) => C turns into A => f(A,_) => f(B) ????

And it would be inept to combine this application into one function as follows:

f:A=>B=>C will f(A,B) ?

Maybe the syntax just confused me here, but it would be great if someone could point out what I am missing here.

thanks

Answer 1

Hopefully this fully working example with a bunch of comments is easy to understand. Answer if you have questions.

You can execute this code by dropping it in the Scala interpreter.

 // Here a trait encapsulating the definition your coworker sent. trait Given { def curry[A,B,C](f:(A,B) => C) : A => B => C def uncurry[A,B,C](f:A => B => C): (A,B) => C } object Impl extends Given { // I'm going to implement uncurry first because it the easier of the // two to understand. The bit in curly braces after the equal sign is a // function literal which takes two arguments and applies the to (ie // uses it as the arguments for) a function which returns a function. // It then passes the second argument to the returned function. // Finally it returns the value of the second function. def uncurry[A,B,C](f:A => B => C): (A,B) => C = { (a: A, b: B) => f(a)(b) } // The bit in curly braces after the equal sign is a function literal // which takes one argument and returns a new function. Ie, curry() // returns a function which when called returns another function def curry[A,B,C](f:(A,B) => C) : A => B => C = { (a: A) => { (b: B) => f(a,b) } } } def add(a: Int, b: Long): Double = a.toDouble + b val spicyAdd = Impl.curry(add) println(spicyAdd(1)(2L)) // prints "3.0" val increment = spicyAdd(1) // increment holds a function which takes a long and adds 1 to it. println(increment(1L)) // prints "2.0" val unspicedAdd = Impl.uncurry(spicyAdd) println(unspicedAdd(4, 5L)) // prints "9.0" 

What about a less numerical example?

 def log(level: String, message: String) { println("%s: %s".format(level, message)) } val spicyLog = Impl.curry(log) // spicyLog type is String => Unit val logDebug = spicyLog("debug") // This new function will always prefix the log // message with "debug". val logWarn = spicyLog("warn") // This new function will always prefix the log // message with "warn". logDebug("Hi, sc_ray!") // prints "debug: Hi, sc_ray!" logWarn("Something is wrong.") // prints "warn: Something is wrong." 

Update You answered: "How the compiler evaluates expressions such as a => b => f(a,b) ." Well, that is not so. At least, as it is defined in a fragment of your colleague who will not compile. In general, however, if you see something like the form A => B => C , which means "a function that takes A as an argument, it returns a function that takes B as an argument and returns C."

Answer 2

I'm not sure that I really understand your question - what would you like to know, besides the actual implementation? As described, this should be pretty trivial:

 def curry[A,B,C](f:(A,B) => C): A => B => C = a => b => f(a,b) 

What does a => b => f(a,b) mean is a function of one argument a whose return value is b => f(a,b) , which again is a function of one argument b , the return value of which you get, you execute f(a,b) (whose type is C ) "

a => b => f(a, b) can be written in a little more detail, if that helps?

  { (a: A) => { // a function of *one* argument, `a` (b: B) => { // a function of *one* argument, `b` f(a, b) // whose return value is what you get of you execute `f(a,b)` (whose type is `C`) } } } 

and

 def uncurry[A,B,C](f:A => B => C): (A,B) => C = (a, b) => f(a)(b) 

Where (a, b) => f(a)(b) means: "A function of two arguments (a, b) , the return value of which is obtained when you first apply a to HoF f , which returns a function, which in turn consumes b to return a C ".

Does it help?