LINUX.ORG.RU

Компиляторы и стек


0

0

Почему наивная реализация Фибоначчи для GHC падает с переполнением стека уже на fib 10, а аналогичная версия на Python без проблем считает fib(40)?

★★★★★

Re: Компиляторы и стек

Есть подозрение что из за ленивости.

imp ★★ ()

Re: Компиляторы и стек

-fcontext-stack ?

anonymous ()

Re: Компиляторы и стек

> Почему наивная реализация Фибоначчи для GHC падает с переполнением стека уже на fib 10, а > аналогичная версия на Python без проблем считает fib(40)?
Код плз. GHC /= GHCi. Также есть +RTS параметры
$ cat a.hs 
fib 0 = 1
fib 1 = 1
fib n = fib(n-1) + fib (n-2)

main = mapM_ (\n -> (putStrLn.show) (n, fib n)) [1..]
$ ghc --make a.hs 
$./a 
(1,1)
(2,2)
(3,3)
(4,5)
(5,8)
(6,13)
(7,21)
(8,34)
(9,55)
(10,89)
(11,144)
(12,233)
(13,377)
(14,610)
(15,987)
(16,1597)
(17,2584)
(18,4181)
(19,6765)
(20,10946)
(21,17711)
(22,28657)
(23,46368)
(24,75025)
(25,121393)
(26,196418)
(27,317811)
(28,514229)
(29,832040)
(30,1346269)
(31,2178309)
(32,3524578)
(33,5702887)
(34,9227465)
(35,14930352)
... [and still counting]

$ghci a.hs
GHCi, version 6.8.3: http://www.haskell.org/ghc/  :? for help
Loading package base ... linking ... done.
Ok, modules loaded: Main.
Prelude Main> main
(1,1)
(2,2)
(3,3)
(4,5)
(5,8)
(6,13)
(7,21)
(8,34)
(9,55)
(10,89)
(11,144)
(12,233)
(13,377)
(14,610)
(15,987)
(16,1597)
(17,2584)
(18,4181)
(19,6765)
(20,10946)
(21,17711)
(22,28657)
(23,46368)
(24,75025)
(25,121393)
(26,196418)
(27,317811)
(28,514229)
(29,832040)
(30,1346269)
(31,2178309)
(32,3524578)
... [all the same]

sf ★★★ ()
Ответ на: Re: Компиляторы и стек от sf

Re: Компиляторы и стек

кажется понял, в чём проблема. Ошибка появляется в ghci, если все клозы функции определять через let, а если через ;, то работает нормально

seiken ★★★★★ ()
Ответ на: Re: Компиляторы и стек от seiken

Re: Компиляторы и стек

Что-то у меня большие подозрения.

Prelude> let { fib 0 = 1; fib 1 = 1; fib n = fib (n-1) + fib (n-2); } in fib 20
10946
Prelude> let { fib 0 = 1; fib 1 = 1; fib n = fib (n-1) + fib (n-2); } in fib 30
1346269

Или имеется ввиду что-то вроде:
Prelude>  let fib 0 = 1
Prelude>  let fib 1 = 1

То так просто нельзя, так как это скорее аналог фигни типа:
main = do let fib 0 = 1
               let fib 1 = 1 -- whoops
               putStrLn $ show $ fib 0

sf ★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.