Как избежать ошибки переполнения стека в Haskell

Question

Я хочу сделать эту функцию:

вызов customPower 2 2 вернет 2 ^ 2 + 2 ^ 1 + 1

вызов customPower 33 вернул бы 3 ^ 3 + 3 ^ 2 + 3 ^ 1 + 1

Вот мой код:

customPower :: Int -> Int -> Int
customPower x y
          | y == 0 = 1
          | y > 0 = (x^(y)) + (customPower x y-1)

Это дает мне исключение переполнения стека, и я могу 'не найти где ошибка.Все вроде нормально.

Answer 1

Операторы имеют более низкий приоритет, чем вызовы функций, это означает, что ваш рекурсивный вызов:

... + (customPower x y-1)

интерпретируется как:

... + ((customPower x y)-1)

, поэтому вы продолжаете звонить с те же самые параметры , поэтому рекурсия никогда не может закончиться.

Мы можем исправить это, добавив скобки для y-1:

customPower :: Int -> Int -> Int
customPower x y
    | y > 0 = x^y + customPower x <b>(y-1)</b>
    | otherwise = 1

С этими модификациями мы не застреваем вбесконечный цикл:

Prelude> customPower 5 3
156 

Мы можем переписать вышесказанное, используя sum :: Num a => [a] -> a и map :: (a -> b) -> [a] -> [b] для реализации этого с однострочником:

customPower :: (Num a, Integral b) => a -> b -> a
customPower x y = sum (map (x^) [0..y])

или мы можем использовать iterate :: (a -> a) -> a -> [a]:

customPower :: (Num a, Integral b) => a -> b -> a
customPower x y = sum (take (y+1) (iterate (x*) 1))

Из-за лени Хаскелла, приведенные выше попытки, скорее всего, все равно приведут к стеку вызовов, который масштабируется линейно со значением y: функции, как говорит @dfeuer, не являются хвостовыми рекурсивными функциями, однако мы можем работать здесь с аккумулятором:

customPower :: Int -> Int -> Int
customPower x = go 1
    where go a y | y > 1 = a
                 | otherwise = seq a (go (a+x^y) (y-1))

, так как вышеуказанная сумма равна простой формуле, мы можем даже вычислить значение в O (y log x) :

   y
.————            y+1
 ╲     i       x    - 1
 ╱    x    =   ————————
*————            x - 1
  i=0

Таким образом, мы можем вычислить значение с помощью:

customPower :: (Integral a, Integral b) => a -> b -> a
customPower x y = div (x^(y+1) - 1) (x - 1)

Обычно это будет работать быстрее, хотя в редком случае, когдарезультат x -1 больше максимального представимого числа типа a, это приведет к переполнению и вернет неправильный номер.