степенная функция haskell

Question

как написать степенную функцию, которая использует следующие факты: Чтобы поднять x до степени n (где n - положительное целое число), если n четное, вы можете найти n-ую степень x, возведя в квадрат наполовину эта сила. Например, x ^ 12 - это x ^ 6 * x ^ 6. Для нечетных степеней просто вычтите единицу из степени и умножьте результат для меньшей степени на x. например, x ^ 13 - это x * x ^ 12, то есть x * x ^ 6 * x ^ 6. Рекурсивно, любая сила может быть найдена с меньшим количеством работы, чем умножение х на указанное количество раз. Я придумал это

power x n
    | n == 0  =  1
    | x == 0  =  0
    | even n = ( power x (n / 2) ) * ( power x (n / 2) )
    | odd n = x * ( power x ((n - 1) / 2)) * ( power x ((n - 1) / 2) )

но я получаю сообщение об ошибке ERROR - Unresolved overloading * Тип: (Интеграл а, Дробный а) => Целое число * Выражение: мощность 2 2

Answer 1

То, что произошло здесь, является распространенным несоответствием типов.Сначала взгляните на сигнатуру типа для even: even :: (Integral a) => a -> Bool.odd имеет аналогичную подпись.Таким образом, вы можете видеть, что even и odd берут любой тип класса типов Integral и оценивают его.Тогда посмотрите на подпись для /: (/) :: (Fractional a) => a -> a -> a./ принимает только Fractional типов, а не Integral.Невозможно, чтобы один тип был оценен обеими этими функциями.В этом случае есть простое решение: используйте div вместо /.Обратите внимание, что если вы используете div в качестве инфиксной функции (поместите ее между аргументами), вам нужно будет ставить обратные метки вокруг div.

Answer 2

Посмотрите на тип even и сравните его с типом /.

Answer 3

Просто замечание, что ваш код работает: Haskell не автоматически запоминает функции, поэтому вы рассчитываете рекурсивные вызовы power дважды в последних двух строках. Я бы порекомендовал ввести простую функцию sqr k = k * k и использовать ее. Есть несколько способов: отдельная функция; пункт where; и let.

Я бы предпочел let:

power _ 0 = 1
power 0 _ = 0
power x n  = let sqr k = k * k
                 half_n = n `div` 2  
                 sqrHalfPower = sqr ( power x half_n )
             in if even n then sqrHalfPower else x * sqrHalfPower 

Как вы видите сделки сопоставления с образцами в первых двух случаях. Тогда let определяет некоторые полезные выражения, которые можно использовать позже в in. Обратите внимание, что для нечетных чисел (n-1) `div` 2 дает тот же результат, что и n `div` 2, поэтому мы можем объединить оба случая.

Answer 4

Я думаю, самый быстрый способ расчета мощности:

     pow:: Integer->Integer->Integer
     pow x n  |(n==1) = x
              |even n = (pow x ( div n 2))*(pow x ( div n 2)) 
              |odd n  = x * (pow x (n-1))

Вы также можете использовать «Int» вместо «Integer» (замените Integer на Int в подписи!).