how to define a structural type that refers to itself?

Question

I want to create a method sum that I can call on different types, specifically sum(1,2).

def sum[A](a1: A, a2: A) = a1 + a2

This fails because the compiler can't tell if A has a method '+'

I tried to define a structural type:

type Addable = {def +(a: Addable)}

This fails because of an illegal cyclic reference

How can I achieve this in a type safe way without requiring A to extend a specific trait?

Answer 1

Scala does not support recursive type aliases without additional compiler arguments (specifically, -Yrecursion). This is partially to keep the type checker at least somewhat in the realm of decidability (though, as we have discovered, the type system is Turing Complete even without recursive type aliases, so it doesn't much matter).

The correct way to do this sort of thing is with a typeclass. Scala encodes these as implicit view bounds. For example:

trait Addable[A] {
  def zero: A
  def add(x: A, y: A): A
}

implicit object IntAddable extends Addable[Int] {
  def zero = 0
  def add(x: Int, y: Int) = x + y
}

implicit object DoubleAddable extends Addable[Double] {
  def zero = 0
  def add(x: Double, y: Double) = x + y
}

// ...

def sum[A](x: A, y: A)(implicit tc: Addable[A]) = tc.add(x, y)

And of course, this also allows you to do fancy things like sum the contents of a Seq in a type-safe manner:

implicit def summableSeqSyntax[A](seq: Seq[A])(implicit tc: Addable[A]) = new {
  def sum = seq.foldLeft(tc.zero)(tc.add)
}

List(1, 2, 3, 4).sum        // => 10
List(true, false).sum       // does not compile

It is worth noting that Scala 2.8 has something very close to this with the Numeric typeclass.