[Haskell-cafe] how to make it faster ?

Richard O'Keefe ok at cs.otago.ac.nz
Wed Mar 24 16:39:14 EDT 2010

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)]

More information about the Haskell-Cafe mailing list