fast_fib.hs

-- Calculating a Fibonacci number (see: http://en.wikipedia.org/wiki/Fibonacci_number)
fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

-- Solving a quiz, I needed to generate a Fibonacci sequence up to a certain limit, e.g. fib n < limit
-- Usual recursion here is expensive and inefficient, takes too long.
fibLst :: Integer -> [Integer]
fibLst 0 = []
fibLst n = fibLst (n-1) ++ [fib n]

-- Accumulating the result here is much better
fibAcc :: Integer -> Integer -> Integer -> [Integer]
fibAcc x y lmt | (x + y) < lmt = (x+y) : fibAcc y (x+y) lmt
               | otherwise = []

{-|
-- < 1 sec to run
*Main> fibAcc 0 1 40000000000000000
[1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906]

-- fibLst 80 would take forever.
|-}