On Nov 5, 2007 5:22 PM, gitulyar
Please help me. I'm new in Haskell programming, but wrote some things in Scheme. I make so function:
fib 1 = 1 fib 2 = 2 fib n = fib (n-1) + fib (n-2)
And when I call "fib 30" it works about 5 seconds. As for me it's really TOO SLOW.
Tell me please if I have something missed, maybe some compiler (interpretaitor) options (I use ghc 6.6.1).
P.S. As I understand function "fib n" should be calculated one time. For example if I call "fib 30" compiler builds tree in which call function "fib 28" 2 times and so on. But as for lazy calculation principle it should be calculated just ones and then it's value is used for all other calls of this function with the same argument. But it seems that this principle doesn't
work in this algorithm. Lazy evaluation is not the same thing as memoization. This algorithm for calculating fibonacci numbers is just as inefficient in Haskell as it is in any other language. Lazy evaluation has to do with *when* things get executed, not saving the values of function calls to be used in place of other calls with the same arguments. For a more efficient Haskell implementation of fibonacci numbers, try fibs :: [Integer] fibs = 1 : 1 : zipWith (+) fibs (tail fibs) fib n = fibs !! n -Brent