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

[Daniel Fischer]

Am Donnerstag 27 August 2009 21:41:49 schrieb 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)

Should be

fibs = 0:1:zipWith (+) fibs (tail fibs)

of course.

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