<br><div class="gmail_quote">On Nov 5, 2007 5:22 PM, gitulyar <<a href="mailto:gitulyar@gmail.com">gitulyar@gmail.com</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>Please help me. I'm new in Haskell programming, but wrote some things in<br>Scheme. I make so function:<br><br>fib 1 = 1<br>fib 2 = 2<br>fib n = fib (n-1) + fib (n-2)<br><br>And when I call "fib 30" it works about 5 seconds. As for me it's really TOO
<br>SLOW.<br><br>Tell me please if I have something missed, maybe some compiler<br>(interpretaitor) options (I use ghc 6.6.1).<br><br>P.S. As I understand function "fib n" should be calculated one time. For<br>example if I call "fib 30" compiler builds tree in which call function "fib
<br>28" 2 times and so on. But as for lazy calculation principle it should be<br>calculated just ones and then it's value is used for all other calls of this<br>function with the same argument. But it seems that this principle doesn't
</blockquote><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">work in this algorithm.</blockquote><div><br>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.
<br><br>For a more efficient Haskell implementation of fibonacci numbers, try<br><br>fibs :: [Integer]<br>fibs = 1 : 1 : zipWith (+) fibs (tail fibs)<br><br>fib n = fibs !! n<br></div><br>-Brent</div>