# A generic interpolate method using type classes

In a previous post I wrote about different `interpolate` methods in my program for linearly interpolating numbers and vectors. The methods for numbers and vectors are exactly the same, except for the types of the arguments and return value. So, ofcourse I wanted to write a generic `interpolate` method to avoid repeating myself.

For a type `V` to be useable by the `interpolate` method, it must satisfy two requirements:

1. It can be multiplied by a number, resulting in a `V`.
2. You can add two `V`s together, resulting in a `V`.

I started with the idea to do this with a structural type (despite the performance disadvantage that structural types suffer from because methods are called via reflection – I just wanted to know if this could work in principle).

The requirements on the type can be described by a structural type directly, and then the `interpolate` method can be written in terms of the type `V`:

```trait Container {
type V = {
def *(t: Double): V
def +(v: V): V
}

def interpolate(t: Double, a: V, b: V): V = a * (1.0 - t) + b * t
}
```

That looks straightforward. But unfortunately, it doesn’t work…

```<console>:8: error: recursive method + needs result type
def +(v: V): V
^
<console>:7: error: recursive method * needs result type
def *(t: Double): V
^
```

Note that the methods `*` and `+` in the type `V` refer to the type itself. Unfortunately, this is not allowed: structural types cannot be recursive, and that’s why you get these error messages. It’s impossible to use a structural type for the generic `interpolate` method.

On StackOverflow, oxbow_lakes put me on another track: you can do this with type classes. Type classes are an idea that comes from Haskell. The description on Wikipedia reads a bit academic and abstract, but the idea is really simple: a type class is simply a type that specifies some property of other types (it classifies types). Have a look at these two type classes, for example:

```// A Multipliable is something that can be multiplied with a T, resulting in an R
trait Multipliable[-T, +R] { def *(value: T): R }

// An Addable is something that you can add a T to, resulting in an R
trait Addable[-T, +R] { def +(value: T): R }
```

These two can be combined into a type class `Interpolatable`, which satisfies the two requirements that are necessary for the `interpolate` method:

```trait Interpolatable[T] extends Multipliable[Double, T] with Addable[T, T]
```

The `interpolate` method can now be written using this type class as follows:

```def interpolate[T <% Interpolatable[T]](t: Double, a: T, b: T): T = a * (1.0 - t) + b * t
```

So, now we have a generic `interpolate` method that works on anything that can be viewed as an `Interpolatable[T]` (note the view bound, specified using `<%`). Ofcourse you now have to tell Scala that a type you want to use this with can indeed be viewed as an `Interpolatable[T]`; this can be done with an implicit conversion. For example for `Double` you can put the following implicit conversion somewhere so that it’s in scope:

```implicit def doubleToInterpolatable(v1: Double) = new Interpolatable[Double] {
def *(t: Double): Double = v1 * t
def +(v2: Double): Double = v1 + v2
}
```

This all works great, but note that all in all we didn’t gain much with this approach. Although the `interpolate` method is generic, it’s still necessary to write an implicit conversion for each type that we want to use with the generic method – the repetition has simply shifted from the `interpolate` method itself to the implicit conversions that we have to write. In principle, though, the approach is valuable; `interpolate` is just a simple example. Suppose that you’d have a much larger and more complicated method than `interpolate`, then using this approach with type classes would really be worth it.

Here’s an interesting presentation by Daniel Spiewak in which he also talks about type classes.

A sidestep to C++

Note that in C++, using templates, it’s very easy to write a generic `interpolate` function that works on any type that satisfies the requirements, and you don’t need to specify this for each type that you want to use:

```template <class T>
T interpolate(double t, T a, T b) {
return a * (1.0 - t) + b * t;
}
```

There’s a big difference between templates in C++ and generics in Scala or Java. A template in C++ is used to generate code for some concrete type at the moment its necessary, and the compiler checks if the code generated from the template is valid (which it is if the concrete type satisfies the requirements). For example, if you use the template on `double`s, the compiler generates an instance of the template specifically for `double`:

```double interpolate(double t, double a, double b) {
return a * (1.0 - t) + b * t;
}
```

In C++ there is no need to explicitly specify what the `*` and `+` functions do for the types that you want to interpolate; they automatically fall into place in the generated code.

1. acherm