[Haskell-cafe] Re: About Fibonacci again...
The Rabbit Sequence: 1,0,1,1,0,1,0,1,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,1,0,1,0,1,1,0,1,1,0,... This nasty acquaintance of mine asked the students to write down a simple procedure which generates the sequence after the infinite number of units of time. Of course, any finite prefix of it. In terms of limits of morphisms we can simply write limit h w = l where l = f w ++ f (tail l) f = concatMap ((!!) h) rabbit = limit [[1],[1,0]] [1] Some other well known sequences: fibonacci = limit [[0,1],[0]] [0] thue_morse = limit [[0,1],[1,0]] [0] cubic_free = limit [[0,1,2],[0,2],[1]] [0] Of course, we have map (1-) rabbit == fibonacci /BR ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: About Fibonacci again...
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
