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

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

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

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

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

Ответ 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.

Ответ 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, благодаря чудесам неявного преобразования. Хотя это правда, что эта функция технически менее гибкая, чем наша структурно типизированная версия, она значительно более эффективна и в высшей степени более читаема. Возможно, мы потеряли способность вычислять теорему Пифагора для непредвиденных типов, определяющих + и *, но я не думаю, что вы пропустите эту способность.

Ответ 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. Я получил frustratringly close!

Ответ 4

В java.lang.Math есть метод:

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);