[Haskell-cafe] About Fibonacci again...
jerzy.karczmarczuk at info.unicaen.fr
jerzy.karczmarczuk at info.unicaen.fr
Wed Nov 7 18:56:46 EST 2007
Don't shoot me...
The last exchange with Andrew Bromage made me recall a homework which was
given to some students by a particularly nasty teacher I happen to know.
The question is to generate the whole infinite Rabbit Sequence in one
shot (co-recursive, selbstverständlich).
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,...
may be obtained in two ways.
A.
1. Begin with one *young* rabbit: 0.
2. In one unit of time a young rabbit grows, becomes *old*: 1.
3. In one unit of time an old rabbit has an offspring, transmutes into [1,0]
(Yes, the rewriting order is meaningful).
The evelution continues...
So, after three units we have: 1 0 1. After four: 10110. Then 10110101. Etc.
B.
The n-th instance fulfils the recurrence
rs 0 = [0]
rs 1 = [1]
rs n = rs (n-1) ++ rs (n-2)
===
That's it, you see now what is the relation between the Rabbit Sequence
and Fibonacci.
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.
The pedagogical result was a disaster. Some students began to work, but
then the teacher went crazy and demanded the solution (in Haskell) as
a one-liner. Just one line, and standard Prelude functions, nothing more.
So, the students thought that if it is a one liner, it must be stupid, and
abandoned this exercise.
Would somebody try to solve it, before I unveil the solution? It isn't
difficult.
Jerzy Karczmarczuk
More information about the Haskell-Cafe
mailing list