Re[Haskell-cafe] duction Sequence of simple Fibonacci sequence implementation

[Jason Dagit]

On Thu, Aug 27, 2009 at 12:32 PM, Bulat
Ziganshin<bulat.ziganshin at gmail.com> wrote:
> Hello SimonK77,
>
> Thursday, August 27, 2009, 11:24:14 PM, you wrote:
>
> for linear timing it needs memoization of previous results. haskell
> compilers doesn't do it automatically since it may change space
> properties of program. well-known example is:
>
> main = print (sum[1..1000] + prod[1..1000])
>
> in order to use memoization you should declare fib as array:
>
> fib = array (1,999) ([1,1]++map (\i -> fib!(i-1) + fib!(i-2)) [3..999])

Unless I'm mistaken this one is also memoized and simpler:
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

Then to get a specific fib, zero index, you do:
fib n = fibs !! n

Jason