Azavea Labs

Where software engineering meets GIS.

Scala’s Numeric type class (Pt. 1)

So I’ve been spending my R&D time recently working on improving Scala’s Numeric type class. We’re about to release an improved version of Numeric, and there’s also an incubator project aimed at getting it integrated into the Scala project. To explain the project (and in preparation for Scalathon in July) I have embarked on writing some blog posts to explain what Numeric is, what it does, and how it can be made better.

These posts will assume you know a bit of Scala, but I will try to keep the discussion as general as I can.

The Goal

The goal seems simple: to implement an algorithm but without choosing in advance which numeric type (e.g. int) to use, and without paying a performance penalty over a “direct” implementation.

Most dynamically-typed languages get this “for free” (in the sense that they pay a performance penalty regardless) and some statically-typed languages can accomplish this with macros, but I will focus on another approach: type classes. I will explain how Scala is able to transcend its Java roots and accomplish this task using the Numeric type class.

Java background

If you work with Java, you probably never write functions which can operate on both integral and floating point values.

Or at least, you probably never support both with one function–in that case you’d have to use java.lang.Number, which is implemented by Java’s boxed primitive types (java.lang.Integer, java.lang.Double) and which only gives you accessors for the various primitive types. It’s a mess:

public class Foo {
    public static Number add(Number t, Number u) {
        return new Double(t.doubleValue() + u.doubleValue());
    }
 
    public static void main(String[] args) {
        Number a = Foo.add(new Integer(3), new Integer(4));
        System.out.println(a.intValue());
    }
}

This code won’t work with some long values, and it basically forces the implementation to choose a primitive type that it hopes will work with the values it will be given (or to use java.math.BigDecimal for everything and incur even more slowness).

You might just support double and call it a day. Or you might write one version to deal with int and then copy-paste the same code but change all the int types to double, etc.. No matter what, the whole exercise feels icky.

Scala background

Scala tries to cover up some of Java warts by combining the notion of primitive types (int) and boxed types (java.lang.Integer) into a single unified type (Int). Scala’s Int type uses int when possible, but will transform them into java.lang.Integer instances behind the scenes if necessary. This makes boxing less annoying to do, but doesn’t make it any faster.

It also doesn’t directly help us accomplish our goal. Int and Double don’t share an interface which exposes things like + so we can’t usefully abstract across their types. In fact, they don’t share any superclass short of AnyVal so we can’t even implement something like our Java solution. (This isn’t totally correct–we can use Java’s types from Scala–but you get the idea.) So what gives? Is Scala even worse than Java when it comes to generic numbers?

No. Scala has more tools at its disposal than Java, and we can get around this problem using one of them: type classes.

Type classes in Scala

In Java, if you want a class to satisfy an interface, the class must be written with knowledge of the interface. When you create new interfaces, you have to go back and modify any classes which should implement them. If you’re using someone else’s classes and they don’t know about your interface, too bad!

This makes using other people’s code harder, and also locks you into someone else’s (possibly poorly-thought-out) type hierarchies. While I am not claiming that the type hierarchy for Scala’s numeric types is poorly-thought-out, it is certainly inconvenient for what we want to accomplish.

Type classes (introduced in the Haskell programming language) offer an alternative approach. Type classes are not interfaces which classes must implement. Instead a type class requires an instance to “glue” each member to the type class. When I say “glue” the member classes to the type class, I mean that each instance will provide the methods that the type class requires in terms of a particular member class. For example, if I have a Flammable type class and a House class, I can create a HouseIsFlammable instance that specifies how the House class satisfies Flammable.

We can implement type classes in Scala using implicit parameters. The basic idea is that we create a trait (Flammable[T]), along with implicit objects which “glue” the supported classes to new our type class (e.g. WoodIsFlammable). Each object corresponds to a single supported class (e.g. Wood). It implements the trait in terms of that class (e.g. Flammable[Wood]), and implements the trait’s methods (e.g. burn) in terms of the supported class.

Then when we want to use the type class, we make sure the instances are in scope and Scala’s compiler will automatically pick up those instances for us.

case class Alcohol(liters:Double)
case class Water(liters:Double)
 
case class Fire(heat:Double)
trait Flammable[A] {
  def burn(fuel:A): Fire
}
 
implicit object AlcoholIsFlammable extends Flammable[Alcohol] {
  def burn(fuel:Alcohol) = Fire(120.0)
}
 
def setFire[T](fuel:T)(implicit f:Flammable[T]) = f.burn(fuel)
 
setFire(Alcohol(1.0)) // ok
setFire(Water(1.0)) // FAIL

This is great! Notice that our Alcohol class doesn’t have to know that it is flammable; we just need to make sure that AlcoholIsFlammable is in scope whenever we want to pass Alcohol to setFire().

This is the exact approach that Scala takes: it defines a Numeric type class along with implicit objects that glue various types (like Int) to the type class.

For instance in Scala 2.8 (and later) this function will square the given number:

def square[T](a:T)(implicit n:Numeric[T]) = n.times(a, a)

Notice that we call the methods we’re interested in (e.g. times()) via the instance of our type class (n) and not the actual values that belong to the typeclass (a). Also, we don’t use a traditional type bound on T, but rather, requiring that an implicit object of type Numeric[T] can be found.

Numeric is part of the Standard Scala Library but unfortunately it does not seem to be widely used. I believe there are several reasons for this:

  1. You can’t do this stuff in Java so people are used to working around the problem.
  2. Using type classes in Scala can be a little bit confusing and cumbersome.
  3. Scala’s Numeric lacks important features (e.g. division).
  4. Scala’s Numeric is slow.

In my next blog post, I will explain how to use the Numeric type class in more detail, point out the problems I’m alluding to, and present our improved version along with some benchmarking numbers.