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