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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
