apfelmus apfelmus at quantentunnel.de
Thu Nov 8 10:00:31 EST 2007

```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

```