[Haskell-cafe] how to make it faster ?

[Richard O'Keefe]

On Mar 24, 2010, at 6:01 PM, 国平张 wrote:

> Hi,
>
> I wrote a type program to compute fibonacci series,

It certainly is possible to compute Fibonacci numbers
as a "type program", but what you wrote is not a type
program, just plain old Haskell.

> if the max value
> is big, then it becomes very slow.
> like
>
> take 100 fib
>
> How can I make it faster :-)

Don't do it that way.  Each element of your list is
computed independently, and each computation takes
exponential time (and would in C or Java).

There are well known ways to compute Fibonacci
numbers in linear and logarithmic time (assuming
integer operations are constant time, which of course
isn't true for big enough integers).  They work well
in Haskell too.

The simplest thing -in Haskell- is to make the
list element computations share the work using
lazy evaluation.

fibs :: [Integer]
fibs = 1 : 1 : [x+y | (x,y) <- zip fibs (tail fibs)]