On Nov 5, 2007 5:22 PM, gitulyar <[EMAIL PROTECTED]> wrote: > > 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
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
