Как написать теорему Пифагора в Scala?

Question

Квадрат гипотенузы прямоугольного треугольника равен сумме квадратов с двух других сторон.

Это теорема Пифагора. Функция для вычисления гипотенузы на основе длины "a" и "b" ее сторон вернет sqrt (a * a + b * b).

Вопрос в том, как бы вы определили такую ​​функцию в Scala таким образом, чтобы ее можно было использовать с любым типом, реализующим соответствующие методы?

Для контекста представьте целую библиотеку математических теорем, которую вы хотите использовать с типами Int, Double, Int-Rational, Double-Rational, BigInt или BigInt-Rational в зависимости от того, что вы делаете, а также от скорости, точности и точности и требования к дальности.

Answer 1

Это работает только в Scala 2.8, но работает:

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

В более общем смысле, черта Numeric фактически является ссылкой на то, как решить этот тип проблемы. Смотри также Ordering.

Answer 2

Самый очевидный способ:

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)

Это ужасно по многим причинам. Во-первых, у нас есть проблема рекурсивного типа Num. Это допустимо только в том случае, если вы компилируете этот код с параметром -Xrecursive, для которого установлено некоторое целое значение (5, вероятно, более чем достаточно для чисел). Во-вторых, тип Num является структурным, что означает, что любое использование определенных им членов будет скомпилировано в соответствующие рефлексивные вызовы. Мягко говоря, эта версия pyth непристойно неэффективна и работает в несколько раз в сто тысяч медленнее, чем обычная реализация. Однако нет никакого способа обойти структурный тип, если вы хотите определить pyth для любого типа , который определяет +, * и для которого существует функция sqrt.

Наконец, мы подошли к самому фундаментальному вопросу: он слишком сложный. Зачем реализовывать эту функцию таким образом? Практически говоря, единственные типы, к которым он когда-либо должен применяться, - это реальные числа Scala. Таким образом, проще всего сделать следующее:

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

Все проблемы решены! Эта функция применима к значениям типа Double, Int, Float, даже к нечетным, таким как Short, благодаря чудесам неявного преобразования. Хотя это правда, что эта функция технически менее гибкая, чем наша структурно типизированная версия, она значительно более эффективна и в высшей степени удобочитаема. Возможно, мы потеряли способность вычислять теорему Пифагра для непредвиденных типов, определяющих + и *, но я не думаю, что вы упустите эту способность.

Answer 3

Некоторые мысли об ответе Даниила:

Я экспериментировал , чтобы обобщить Numeric до Real, что было бы более подходящим для этой функции для обеспечения функции sqrt. Это приведет к:

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

Использовать литеральные числа в таких обобщенных функциях сложно, но возможно.

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
}

Вывод типа работает лучше, если sqrt передается во втором списке параметров.

Параметры a и b будут передаваться как объекты, но @specialized может это исправить. К сожалению, в математических операциях все еще будут накладные расходы.

Вы можете почти обойтись без импорта mkNumericOps. Я получил очень близко!

Answer 4

В java.lang есть метод. Математика:

public static double hypot (double x, double y)

, для которого javadocs утверждает:

Возвращает sqrt (x2 + y2) без промежуточного или недостаточного переполнения.

, изучая src.zip, Math.hypot использует StrictMath, который является нативным методом:

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