Curried Functions in Scala

In scala, we define a function like this:

def product(a: Int, b: Int): Int = a * b

Then, we call it like:

product(2, 8)

Other than some minor syntax details, this is pretty much the way functions are defined in most of the mainstream languages, such as Java and C#. However, in Scala there is an alternative way of defining this same function:

def product(a: Int)(b: Int): Int = a * b

If we define it this way, we need to call it like:

product(2)(8)

I know, we've just replaced a comma and a space with a closing and an opening parenthesis. Harder to type, so what's the point? It turns out there are a number of reasons to use this alternate form. These include:

• Partial function application
• Type inference
• Block syntax
• Implicit parameters 

The first form of the function definition can be thought of as "a function that takes 2 integers". The parenthesis for precedence are just where they are shown in the definition.

def product(a: Int, b: Int): Int

The 2 parameters are bundled together and passed to the function. However, the second form is left-associative.

 def (product(a: Int))(b: Int): Int

This can be thought of as "a function that takes one integer, and returns a function that takes another integer".

According to Wikipedia, Currying is "The technique of translating the evaluation of a function that takes multiple arguments (or a tuple of arguments) into evaluating a sequence of functions, each with a single argument." So, the second form of the function definition is a curried function.

Partial Function Application

With the curried function in the above example, we can do the following:

val times3 = product(3)_

 times3 is a function that takes an integer and multiplies it by 7. In the REPL:

scala> times3(7)
res6: Int = 21

What we have now is a function that is poised to multiply any other integer by 3.

Note that in some languages, such as Haskell, all functions are curried by default, and partial application happens any time you call a function with fewer than the full number of parameters. However, in Scala, the trailing underscore is needed as a placeholder to allow for partial application.

A partially applied function can be useful in a number of circumstances. For example, if a higher order function accepts a function with fewer parameters than the function you have, you can partially apply it before passing it as a parameter. It can also be used to specialize more general functions, and is a mechanism for function reuse.

If you have an uncurried function, like def sum(a: Int, b: Int): Int = a + b, and need a curried version of it, you can get one like this:

val sumCurry = (sum _).curried

You can also partially apply an uncurried function by using placeholder syntax for the parameters:

val sumPartial = sum(_: Int, 4)

The upside of this technique is that you can partially apply any of the parameters. The downside is that you almost always need to specify the type of the missing parameters, even if they seem obvious.

Many times, the terms currying and partial application are used as though they are synonymous. This is not the case. Currying is the process described by the wikipedia definition above, while partial application refers to providing only a subset of the parameters to a function and getting a function that takes the remaining parameters. So, a curried function can be partially applied, but, at least in Scala, a curried function is not required for partial application. This means that in Scala the remaining points we will discuss with respect to currying are arguably more important than partial application.

Type Inference 

While partial application is something that is common to many languages using the functional paradigm, this topic is specific to Scala. Let's take this function:

def transmogrify[A,B](a: A, f: A=>B):B = f(a)

 Let's see what happens when we call this in the REPL:

scala> transmogrify(3, a => a * 4) 
<console>:9: error: missing parameter type
              transmogrify(3, a => _ * 4)
                              ^

What happened? Surely the Scala compiler can see that the parameter to the third argument must be an integer! But, it can't, so we need to help the compiler out and call it like this:

scala> transmogrify(3, (a: Int) => a * 4) 
res1: Int = 12

While this works, it is an unfortunate amount of boilerplate. The solution is to instead define the function like so:

def transmogrify[A,B](a: A)(f: A => B): B = f(a)

Now we can successfully call it like:

transmogrify(3)(a => a * 4) 

Or, even more succinctly using placeholder syntax:

transmogrify(3)(_ * 4) 

How does this work? Well, in languages like Haskell, the compiler is very good at inferring types - in essence, the type information flows in all directions. However, in Scala, type information flows from left to right across parameter groups (but not within parameter groups) and down into the body of the function. In the case of method calls on objects, the object is treated as it's own (and first) parameter group.

So, in the transmogrify example, Scala sees the parameter in the first parameter group and can determine the type of A, so it knows that the function in the secong parameter group must accept an Integer. I think of it in terms of partial application. Scala first applies the 3 to transmogrify, knows what A is, and is left with a function that accepts another function that accepts an A. So, it knows the type of the argument to that function without us explicitly stating it.

There are, however, instances where currying hurts type inference. For example:

scala> def fold[A,B](o: Option[A])(b: => B)(f: A=>B): B =
  o.fold(b)(f) 
defined function fold

scala> fold(Option(3))(Nil)(List(_)) 
Main.scala:2261: type mismatch;
 found   : List[Int]
 required: scala.collection.immutable.Nil.type
fold(Option(3))(Nil)(List(_))
                         ^

This code is trying to convert an Option to a List. If the Option was None, the list would be empty, otherwise it would be a List with a single item containing the value that was in the Option. However, Scala sees the Nil and sets the type of B to be Nil. When it hits the last parameter group, it sees the List(_), knows this is a List[Int], and gives an error. Why? Because of the way List is defined, Nil is a subtype of every type of list. However, List[Int] is not a Nil. We need to help out with type annotations here:

scala> fold(Option(3))(Nil: List[Int])(List(_)) 
res44: List[Int] = List(3)

However, if we combine the last 2 parameter groups like this:

scala> def fold[A,B](o: Option[A])(b: => B, f: A=>B): B =
  o.fold(b)(f) 
defined function fold

scala> fold(Option(3))(Nil, List(_)) 
res45: List[Int] = List(3)

In this case, Scala sees both Nil and List(_) at the same time, knows they are both supposed to evaluate to the same type (B), and widens Nil to List[Int]. (Thanks to Rob Norris for this example.) Note that this also shows that even with multiple parameter groups, the groups can have more than one parameter in them, which doesn't strictly fit the definition of currying but is similar in intent.

Block Syntax

Any time the last parameter group consists of a single function, block syntax can be used. Let's use the curried version of transmogrify from above as an example:

scala> transmogrify(2){ a =>
     | if (a < 2) "Small"
     | else "Large"
     | }
res7: String = Large

Curly braces are used instead of parenthesis, and the function can be split across multiple lines with no semicolons. Here is an alternate way using the syntactic shortcut for match statements:

scala> transmogrify(2) {
     | case a if a < 2 => "Small"
     | case _ => "Large"
     | }
res8: String = Large

In this case, the use of pattern matching is a bit of an overkill, but it serves as an illustration.

Block syntax, in combination with by-name parameters, is particularly useful for things like creating custom control structures.

Implicit Parameters

It is beyond the scope of this post to go into the details of implicit parameters, so we'll just touch on it briefly. The last parameter group of a function can be denoted as implicit, like so:

def binaryOp[A](a1: A, a2: A)(implicit f: (A,A) => A): A = f(a1, a2)

Then, if we have a value like this in scope:

implicit val tacit = (a1: Int, a2: Int) => a1 + a2 

We can call our function without including that implicit parameter group:

scala> binaryOp(3, 4) 
res6: Int = 7

I'll just note that implicits are very powerful, and as such come with great responsibility. They can be used by library authors to simplify user code, and for implementing such useful things as type classes. But, they can also be used to write extremely obfuscated code. Use with caution.

Note: This blog post is essentially the same information as a beginner's talk I gave at the PDX Scala Meetup on 19 April, 2016.

Ad-Hoc Polymorphism and Typeclasses in Scala, part 3

In part 2, we developed an Equal subclass. Now we'll show how you can use Equal to build up additional typeclasses. We'll start by making a simple function that determines if a list has a value in it. (Part 1 is here.)

def has[A:Equal](as: List[A], a: A): Boolean = {
  as.foldLeft(false)((b, e) => b || e === a)
}

This is similar to the List.contains() method, but uses our Equal typeclass to do the comparison.

val ints: List[Int] = List(1, 2, 3, 4)
val hasIt = has(ints, 3)

However, we'd like to generalize our has function. We'll start by extracting out the concept of FoldLeft into a trait and implementing it for a List.

trait FoldLeft[F[_]] {
  def foldL[A, B](as: F[A], b: B)(f:(B, A) => B): B}

object FoldLeft {

  implicit val foldLeftList: FoldLeft[List] = new FoldLeft[List] {
    def foldL[A, B](as: List[A], b: B)(f: (B, A) => B): B = as.foldLeft(b)(f)
  }

}

The above trait and definition are very similar to what we did with Equal, with one big difference. FoldLeft's type parameter is not a simple value, it is a higher kind. I don't want to dig too deep into kinds now, but I'll give a brief explanation. If you want a better description, I recommend checking out Learn You A Haskell For Great Good.

In trait Equal[A], the A represents a on concrete type. You can create an instance of it directly, such as an Int or a String. In trait FoldLeft[F[_]], the F is a higher kind. It is a type that requires another type before it can be instantiated. For example, List or Option. You can't create a List, but you can create a List[Int].

Now we can modify our has function to use our new trait. (We're skipping a few of the steps we went through in part 2.)

def has[M[_], A](as: M[A], a: A)(implicit eq: Equal[A], fl: FoldLeft[M]): Boolean = {
  fl.foldL(as, false)((b, e) => b || e === a)
}

We can also simplify the function we pass by using the underscore syntax.

def has[M[_], A](as: M[A], a: A)(implicit eq: Equal[A], fl: FoldLeft[M]): Boolean = {
  fl.foldL(as, false)(_ || _ === a)
}

At this point, we still call has the same way. But, we'd like to be able to call it as a method on a list. We can't just use the Identity trait, because it doesn't provide enough type information. So, we'll create a new one. We'll also move the has function into the trait, and provide an implicit conversion method.

trait MA[M[_], A] {
  val value: M[A]

  def has(a: A)(implicit eq: Equal[A], fl: FoldLeft[M]): Boolean = {
    fl.foldL(value, false)(_ || eq.equal(_, a))
  }
}

implicit def toMA[M[_], A](ma: M[A]): MA[M, A] = new MA[M, A] {val value = ma}

Now we can use has like this:

val hasIt = ints has 7

We can go one step further. If our operator ends with a colon, it becomes right associative. In other words, the method will be called on the value to the right of the operator, with the value on the left passed as a parameter.

trait MA[M[_], A] {
  val value: M[A]

  def has(a: A)(implicit eq: Equal[A], fl: FoldLeft[M]): Boolean = {
    fl.foldL(value, false)(_ || eq.equal(_, a))
  }

  def >>:(a: A)(implicit eq: Equal[A], fl: FoldLeft[M]): Boolean = has(a)
}

So, we can use it like this:

val hasIt = 3 >>: ints

We can even make the operator unicode and use the element of unicode symbol.

def ∈:(a: A)(implicit eq: Equal[A], fl: FoldLeft[M]): Boolean = has(a)

val hasIt = 3 ∈: ints

If you do decide to create any unicode operators, I highly recommend providing a "plain text" alternative as well. In fact, you should think hard about creating operators: they should make sense and clarify the code, not make it more obscure.

That's as far as I'm going to go, but it gets much deeper. Check out scalaz or the resources in my acknowledgment section in part 1.

Ad-Hoc Polymorphism and Typeclasses in Scala, part 2

In part 1, we covered the types of polymorphism and how ad-hoc polymorphism works in Haskell. Now, we'll look at implementing it in Scala. We'll start with a basic example and build up to a better solution.

We'll implement an Equal typeclass (Eq in Haskell) that is used for comparing 2 values of the same type. To do this, we'll create a trait and an implementation of it for Ints.

trait Equal[A] {
  def equal(a1: A, a2: A): Boolean
}

class EqualInt extends Equal[Int] {
  def equal(a1: Int, a2: Int): Boolean = a1 == a2
}

We'll also make a function that uses it:

def areTheyEqual[A](a1: A, a2: A, eq: Equal[A]): String = {
  if (eq(a1, a2)) "Yes"
  else "No"
}

OK. It's a lame function, but it should serve our purposes for now. We can call the function like:

val areThey = areTheyEqual(1, 3, new EqualInt)

The function can now compare different types, as long as we pass an implementation for Equal for that type to it. But, it's a far cry from elegant. The next step is to make the Equal parameter implicit. This requires making another parameter group:

def areTheyEqual[A](a1: A, a2: A)(implicit eq: Equal): String ...

We can also define areTheyEqual() using context bound syntax like:

def areTheyEqual[A: Equal](a1: A, a2: A) = {
  if (implicitly[Equal[A]]equal(a1, a2) "Yes"
  else "No"
}

Either way, we can call it like:

val areThey = areTheyEqual(1, 3)(new EqualInt)

But, we can also pass the parameter implicitly if an appropriate value is in scope:

implicit val eq = new EqualInt
val areThey = areTheyEqual(1, 3)

The Scala compiler sees that the implicit parameter is missing, and goes looking for one for us. However, at this point we still need to create the missing implicit value. To make this easier, we'll put some default implicit values in the companion object for the Equal trait. If the compiler doesn't find an implicit value in the local scope or that is explicitly imported it will check in the companion object. This provides a convenient place to put the default implicit values.

object Equal {
  implicit object EqualInt extends Equal[Int] {
    def equal(a1: Int, a2: Int): Boolean = a == b
}

While the above works in almost all cases, it is better to explicitly give the type of implicit value to avoid some subtle type errors that can occur. You can do that like this (as well as adding an instance for Strings):

object Equal {
  implicit val equalInt: Equal[Int] = new Equal[Int] {
    def equal(a1: Int, a2: Int): Boolean = a == b
  }
  implicit val equalString: Equal[String] = new Equal[String] {
    def equal(a1: String, a2: String): Boolean = a == b
  }
}

The definitions for Int and String are identical here, but that is not the case in general. Now we don't have to create our own implicit val eq = new EqualInt, and we can also use areTheyEqual() for Strings:

val areThey1 = areTheyEqual(1, 3)
val areThey2 = areTheyEqual("xyz", "xyz")

Calling areTheyEqual() for different types is now simple and clean. As a library developer for Equal, you would want to provide a number of default implementations for different types. Users could then make their types "instances" of the Equal "typeclass" in the same way, without needing to alter their type at all.

But, what if you have a need to compare Strings by a different criteria - maybe case insensitive, or you only care about the length of the strings. You can create your own implicit instance, either in the local scope or in a package you explicitly import, and it will take precedence over the one defined in the Equal package:

implicit val equalStrLen: Equal[String] = new Equal[String] {
  def equal(a1: String, a2: String): Boolean = a1.length = a2.length
}

val areThey = areTheyEqual("abc", "xyz") // now is true

Of course, you can also still pass an instance of Equal explicitly:

val areThey = areTheyEqual("abc", "xyz")(equalStrLen)

Ok. That's great. But, one thing is still bothering me. I have to do my comparison like so:

  eq.equal(1, 3)

It would be much nicer to be able to call equal on one of the parameters, like 1.equal(3), or even use something that looks more like an operator: 1 === 3.

So far, we've used the implicit mechanism for passing an implicit parameter. But, there is another way it can be used - for implicitly converting one type to another. This is how Scala allows methods to be called on values like Int, which are not present in the Java implementation of them, while still being compatible with Java. When the Scala compiler sees a method being called on an object, but doesn't find that method defined on the object, it looks around for another class that DOES have that method, and for an implicit method that will convert the original type to that type. In the case of Int, if you type 5 min 7, the compiler sees Int does not have a min method, but it finds an implicit method that converts an Int to a RichInt, which does have that method, so it performs the conversion.

That is essentially what we want to do here, but we want to do it in a more general fashion. So, we'll start by creating a trait that can wrap any kind of value, and an implicit function for doing the conversion:

trait Identity[A] {
 val value: A
}

implicit def toIdentity[A](a: A): Identity[A] = new Identity[A] {val value = a}

So, now we can implicitly convert any type A to an Identity[A], but it doesn't do anything. To remedy this, we can add method definitions to the trait:

trait Identity[A] {
  val value: A

  def ===(a2: A)(implicit eq: Equal[A]) = eq.equal(value, a2)
  def =/=(a2: A)implicit eq: Equal[A]) = !eq.equal(value, a2)
}

The compiler will now allow us to call the === method on any type that can be converted to Identity (which is every type) AND for which there is an implicit Equal[A] available. Now we can use our trait in a much more natural fashion:

1 === 2
"abc" =/= "xyz"

I know what you're thinking: "Great! He just went to a lot of trouble to implement ==, and !=". But, there is one big difference. Equal is type safe. In the Scala REPL, if you use == on 2 different types, you'll see something like this:

scala> 1 == "one"

<console>:11: warning: comparing values of types Int and String using `==' will always yield false

       1 == "one"

         ^

res4: Boolean = false

It emits a warning, but does the comparison anyway. Let's try it with ===.

scala> 1 === "one"

<console>:15: error: type mismatch;

 found   : String("one")

 required: Int

       1 === "one"

             ^

You now get a compiler error if you try to compare dissimilar types.

We can also use the Equal typeclass in other typeclasses. In part 3, we will extend our example.

Ad-Hoc Polymorphism and Typeclasses in Scala, part 1

I recently offered to give a talk on this subject to the PDXScala meetup group in Portland, OR. I was just going to share my slides with participants, but they probably wouldn't have been too useful without my commentary - especially since I'm going to develop most of the code "live" in an editor and sbt. So, I decided to start a blog. It's a big subject for one blog post, so I'll do it in installments.

Roadmap

I'll start out by talking about the OO version of polymorphism most people are familiar with and discuss some of the limitations of it. Then we'll go on to how a language like Haskell, which is not object oriented, manages to have polymorphism anyway. This version of polymorphism is built into the Haskell language, but we'll figure out how we can implement it with Scala.

OO and Subtype Polymorphism

When object oriented programming came along, polymorphism was one of it's key features. By creating a class hierarchy, methods could specify an argument of a base type, but also accept any subtype as the argument. This is the familiar polymorphism that looks like this:

trait Animal {
 def speak: String
}

class Dog extends Animal {
 val speak = "Woof"
}

val dog = new Dog

In Scala you can also create an instance more directly:

val fox = new Animal {val speak = "???"}

And a function that takes an Animal:

def whatDoesItSay(animal: Animal): String = "It says " + animal.speak

val dogSays = whatDoesItSay(dog) 
val foxSays = whatDoesItSay(fox)

We could also write whatDoesItSay with a type constraint:

def whatDoesItSay[A <: Animal](a: A): String = "It says " + a.speak

This provides a great way to achieve flexibility in modelling many real world problems. However, it does have some limitations.

1. All the objects need to be part of a class hierarchy. You need to build the polymorphism into the classes from the start. This also means that you're stuck if you need use classes you can't modify, such as those from a class library.
2. You may need to add functionality to your class which really isn't behavior that belongs in your class. This is a violation of separation of concerns.

True, there are ways around this, such the adapter pattern in which you wrap your class in another class that implements the interface that you require, but this is not an ideal situation. I'm not going to go into this, but Debasish Ghosh talks about this in his blog post Scala Implicits: Type Classes Here I Come.

Note: There is also another form of polymorphism, parametric polymorphism, in which behavior does NOT vary with type. This can be seen in "generic" collections such as List[A]. You can make a List of ANY type - it is type agnostic. Essentially, it does not really interact with it's elements.

Ad-Hoc Polymorphism in Haskell

Since Haskell doesn't have classes, at least not classes in the same manner as Object Oriented languages do, how does it create polymorphism? The answer is typeclasses. I'm going to throw a little Haskell in here. Don't worry if you have trouble following it completely, I know Haskell syntax can be a bit hard to follow. You'll still be able to understand the rest of the post when we get to it. Mostly I want you to see how easy and elegant it is to do this in Haskell.

So, here's how you declare a typeclass:

class Show a where show :: a -> String

Show is actually one of the typeclasses that come with the standard Haskell libraries, but we'll pretend we just made it up. It's very much like this Scala trait:

trait Show[A] {
 def show(a: A): String
}

The Show typeclass declares one function, which converts an object of type A into a string. But how do you make a type part of this typeclass? You just say:

instance Show Bool where
  show True = "True"
  show False = "False"

This makes the Bool type an instance of the Show typeclass. Now you can use boolean values with the show function:

let x = True
let y = show x

Or create a function called showMe that requires an instance of a Show as an argument:

showMe :: (Show a) => a -> String
showMe a = "Is is " + show a

Now we can call showMe with x:

showMe x

Note that you just use the Bool value directly. You don't have to wrap it in an Adapter or anything. The compiler sees that an instance of Show is required and that Bool is an instance of Show and (sort of) takes care of the wrapping for you. It's like having the Adapter pattern baked into the language.

Hmmm. The compiler does the wrapping for us. Does that sound familiar?

Yep. Implicits in Scala. In part 2, we'll cover how to implement this in Scala using implicits.

Acknowledgements

I don't bill myself as a Scala expert, nor is anything I explain in these posts new. I have leaned heavily on a number of websites in preparing my talk and these blog posts, mashing them up a bit. In particular:

Scala Implicits : Type Classes Here I Come by Debasish Ghosh, which talks about typeclasses, the Adapter pattern, and more.

Learning Scalaz which explains scalaz by essentially going through the same steps as Learn You a Haskell.

This Scalaz Talk by Nick Partridge, which is not only excellent, but I attempted to use a similar style in my talk.

Of course if you want to learn about things functional, it doesn't hurt to know a little Haskell. Learn You a Haskell for Great Good is an excellent book.

Last, but not least, check out the source code for scalaz. The project really pushes the limits of what the Scala type system can do.