[Haskell-cafe] Re: About Fibonacci again...

[apfelmus]

It's not over yet, the rabbits are still going strong on the fibonacci-side.

Jerzy Karczmarczuk wrote:
> the solution of Alfonso Acosta:
>
> rs_aa = let acum a1 a2 = a2 ++ acum (a1++a2) a1 in 1 : acum [1] [0]

We can apply the difference list trick to obtain

   f 0 = (0:)
   f 1 = (1:)
   f n = f (n-1) . f (n-2)

i.e.

   rs_aa' = let accum r1 r2 = r2 . accum (r1 . r2) r1
            in 1: accum (1:) (0:) undefined

> Finally, Bernie Pope original:
>
> mrs = [0] : [1] : zipWith (++) (tail mrs) mrs
> rs_bp = [(mrs !! n) !! (n-1) | n <- [1..]]
>
> produced something which also begins with a list of lists. It seems that
> it is faster than the solution of A.B., but I have also the impression
> that it generates a lot of temporary rubbish: the printing of a long
> sequence periodically stops as if GC sneaked in.

and

   mrs' = (0:) : (1:) : zipWith (.) (tail mrs') mrs'

To speed up Bernie's infinite list flattening, we note that for every 
"generalized" fibonacci sequence

      f n = f (n-1) <+> f (n-2)

we have the following telescope "sum"

  f (n+2) = f 1 <+>  f 0 <+> f 1 <+> f 2 <+> ... <+> f n
          = f 2          <+> f 1 <+> f 2 <+> ... <+> f n
          = f 3                  <+> f 2 <+> ... <+> f n

i.e.

  f (n+2) = f 1 <+> foldr1 (<+>) [f k | k <- [0..n]]

This identity allows us to write

      f ∞ = f 1 <+> foldr1 (<+>) [f k | k <- [0..]]

and hence

   rs_bp' = 1: foldr1 (.) mrs' undefined

To close the circle, Alfonso's solution is in fact the deforestation of 
this one.


Regards,
apfelmus