LINUX.ORG.RU
Форум — Development  

Haskell и хвостовая рекурсия

 


0

0

Задачка из SICP по вычислению числа pi с заданной точностью. Как-то странно ведет себя такой код на Haskell, такое впечатление будто хвостовая рекурсия не используется:

prod term a step b = prod' 1 a where
    prod' res curr | curr > b  = res
                   | otherwise = prod' (res * term curr) (step curr)

getPi acc = 8 * (prod (\x -> (x+1)/x) 3 (+2) (2*acc+1))^2 / (2*acc+2)

GHC говорит про переполнение стека при вызове getPi 1000000. Аналогичный код на Scheme ведет себя так как надо, разворачивая вычисления в цикл (судя по дебагу).

Пробовал реализовывать prod через foldl, та же самая фигня. В какую сторону копать?

★

Последнее исправление: maxcom (всего исправлений: 1)

тут утечка памяти из-за ленивости, а не отсутствия хвостовой рекурсии. Грубо говоря вместо числа у тебя хранится вычисление (thunk), который постепенно увеличивается, поэтому и памяти не хватает.

mholub
()
Ответ на: комментарий от exlevan

Скомпилировать с -02, юзать foldl' вместо foldl или сделать prod' строгой по аргументам.

Просто -O2 не помогло, а вот вариант с foldl' и такой помог:

prod term a step b = prod' 1 a where
    prod' res curr | curr > b  = res
                   | otherwise = (prod' $! (res * term curr)) $! (step curr)

А вариант «строгой по аргументам» - это как?

vega ★
() автор топика
Ответ на: комментарий от vega 
prod' !res !curr | curr > b  = res
                 | otherwise = prod' (res * term curr) (step curr)

компилировать с -XBangPatterns, или можно указать тип prod'

prod' :: !Double -> !Double -> !Double
Begemoth ★★★★★
()
Ответ на: комментарий от Begemoth

Попробовал. С -XBangPatterns работает. Но почему-то медленнее, чем вариант с $!. А вот на указание типа prod' компилятор матерится:

    Unexpected strictness annotation: !Double
    In the type signature for `prod'':
      prod' :: !Double -> !Double -> !Double
    In the definition of `prod':
        prod term a step b
               = prod' 1 a
               where
                   prod' :: !Double -> !Double -> !Double
                   prod' res curr
                           | curr > b = res
                           | otherwise = prod' (res * (term curr)) (step curr)
vega ★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development