How does one write the Pythagoras Theorem in Scala?

Question

The square of the hypotenuse of a right triangle is equal to the sum of the squares on the other two sides.

This is Pythagoras's Theorem. A function to calculate the hypotenuse based on the length "a" and "b" of it's sides would return sqrt(a * a + b * b).

The question is, how would you define such a function in Scala in such a way that it could be used with any type implementing the appropriate methods?

For context, imagine a whole library of math theorems you want to use with Int, Double, Int-Rational, Double-Rational, BigInt or BigInt-Rational types depending on what you are doing, and the speed, precision, accuracy and range requirements.

Answer 1

The most obvious way:

type Num = {
  def +(a: Num): Num
  def *(a: Num): Num
}

def pyth[A <: Num](a: A, b: A)(sqrt: A=>A) = sqrt(a * a + b * b)

// usage
pyth(3, 4)(Math.sqrt)

This is horrible for many reasons. First, we have the problem of the recursive type, Num. This is only allowed if you compile this code with the -Xrecursive option set to some integer value (5 is probably more than sufficient for numbers). Second, the type Num is structural, which means that any usage of the members it defines will be compiled into corresponding reflective invocations. Putting it mildly, this version of pyth is obscenely inefficient, running on the order of several hundred thousand times slower than a conventional implementation. There's no way around the structural type though if you want to define pyth for any type which defines +, * and for which there exists a sqrt function.

Finally, we come to the most fundamental issue: it's over-complicated. Why bother implementing the function in this way? Practically speaking, the only types it will ever need to apply to are real Scala numbers. Thus, it's easiest just to do the following:

def pyth(a: Double, b: Double) = Math.sqrt(a * a + b * b)

All problems solved! This function is usable on values of type Double, Int, Float, even odd ones like Short thanks to the marvels of implicit conversion. While it is true that this function is technically less flexible than our structurally-typed version, it is vastly more efficient and eminently more readable. We may have lost the ability to calculate the Pythagrean theorem for unforeseen types defining + and *, but I don't think you're going to miss that ability.

Answer 2

This only works on Scala 2.8, but it does work:

scala> def pythagoras[T](a: T, b: T, sqrt: T => T)(implicit n: Numeric[T]) = {
     | import n.mkNumericOps
     | sqrt(a*a + b*b)
     | }
pythagoras: [T](a: T,b: T,sqrt: (T) => T)(implicit n: Numeric[T])T

scala> def intSqrt(n: Int) = Math.sqrt(n).toInt
intSqrt: (n: Int)Int

scala> pythagoras(3,4, intSqrt)
res0: Int = 5

More generally speaking, the trait Numeric is effectively a reference on how to solve this type of problem. See also Ordering.

Answer 3

There is a method in java.lang.Math:

public static double hypot (double x, double y)

for which the javadocs asserts:

Returns sqrt(x2 +y2) without intermediate overflow or underflow.

looking into src.zip, Math.hypot uses StrictMath, which is a native Method:

public static native double hypot(double x, double y);

Answer 4

Some thoughts on Daniel's answer:

I've experimented to generalize Numeric to Real, which would be more appropriate for this function to provide the sqrt function. This would result in:

def pythagoras[T](a: T, b: T)(implicit n: Real[T]) = {
   import n.mkNumericOps
   (a*a + b*b).sqrt
}

It is tricky, but possible, to use literal numbers in such generic functions.

def pythagoras[T](a: T, b: T)(sqrt: (T => T))(implicit n: Numeric[T]) = {
   import n.mkNumericOps
   implicit val fromInt = n.fromInt _

   //1 * sqrt(a*a + b*b)   Not Possible!
   sqrt(a*a + b*b) * 1    // Possible
}

Type inference works better if the sqrt is passed in a second parameter list.

Parameters a and b would be passed as Objects, but @specialized could fix this. Unfortuantely there will still be some overhead in the math operations.

You can almost do without the import of mkNumericOps. I got frustratringly close!