Haskell - переполнение стека рекурсии - PullRequest
Новая
       38

Haskell - переполнение стека рекурсии

0 голосов
/ 14 февраля 2019

Я пытаюсь сложить все n от 1 до очень большого числа (на данный момент 10 ** 9), но это приводит к переполнению стека.Кроме того, я не думаю, что ставить точку на 1 и делать сумму n в разных строках - это самый эффективный способ, но код ниже - все мои знания для Haskell.Я действительно не знаю много о функциональном программировании, и я хотел бы получить как можно больше объяснений.(Также я попытался поместить $! Strict в последнюю строку, о которой говорилось в других местах, но это ничего не изменило. Я был бы рад, если бы вы объяснили наиболее эффективный способ, которым я мог бы выполнить эту рекурсивную функцию.) 

main :: IO()

summ 1 = 1
summ n = 1/(n**2) + summ (n-1)

expected_value = pi*pi/6
errorPercent n = n / expected_value * 100

main = do
    putStr "%"
    print (errorPercent (summ $! (10**9)))

Ответы [ 2 ]

0 голосов
/ 14 февраля 2019

Чи ответил на один бит вопроса, который, я думаю, является основной проблемой, но есть кое-что еще, что беспокоит меня.Когда вы говорите 10**9, вы получаете число с плавающей запятой (потому что ** - это "дробное" возведение в степень).И затем вы используете равенство с плавающей запятой для проверки базового случая вашей рекурсии.

summ 1 = ...

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

summ 4 =        ... summ 3
summ 3 =        ... summ 2.000001
summ 2.000001 = ... summ 1.000001 
summ 1.000001 = ... summ 0.000001  -- BASE CASE MISSED!
summ 0.000001 = ... summ (-1.000001)
summ (-1.000001) = ... summ (-2.000001)

и так далее.Если вы не получили переполнение стека при вызовах 10 9 , вы наверняка получите бесконечное количество.

Вы должны либо определить свою функцию на целых числах, чтобы не было ошибки округления 

summ :: Int -> Double
summ 1 = 1
summ n = 1 / (fromIntegral n ** 2) + summ (n - 1)
--            ^^^^^^^^^^^^
-- conversion necessary to go from Int to Double

main = ... print (summ (10 ^ 9))
--                      ^^^^^^
--      use integral exponentiation (^) instead of (**)

или используйте более щадящий базовый вариант 

summ :: Double -> Double
summ n | n <= 1 = 1
summ n = 1 / (n ** 2) + summ (n - 1)

В любом случае, вам определенно следует принять предложение Чи сделать это в стиле аккумулятора, а также обязательно поставить подпись типа.

Вот больше о том, как вы получаете переполнение стека в Haskell , если вам интересно.

0 голосов
/ 14 февраля 2019

Проблема здесь в том, что суммы не могут быть начислены до тех пор, пока не завершатся все 10 ^ 9 рекурсивных вызовов.По сути, вы вычисляете 

1/(n**2) + ( 1/((n-1)**2) + ( 1/((n-2)**2) + ....

, а скобки мешают начать суммирование.Вместо этого мы хотели бы иметь 

(( 1/(n**2) + 1/((n-1)**2) ) + 1/((n-2)**2) ) + ....

Самый простой способ - использовать дополнительный аргумент «аккумулятор»: 

summ 1 acc = 1 + acc
summ n acc = summ (n-1) $! acc + 1/(n**2)

main = do
    putStr "%"
    print (errorPercent (summ (10^9) 0))  -- set acc to 0 at the beginning

Для повышения производительности я бы рекомендовал добавитьвведите подпись к summ например summ :: Int -> Double -> Double.

Полная программа ниже.Это работает в 12 секунд здесь (ghc -O2). 

summ :: Int -> Double -> Double
summ 1 acc = 1 + acc
summ n acc = summ (n-1) $! acc + 1 / (fromIntegral n**2)

main :: IO ()
main = do
    putStr "%"
    print (summ (10^9) 0)  -- set acc to 0 at the beginning
...