[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:
may be obtained in two ways. 

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. 

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

Jerzy Karczmarczuk 

More information about the Haskell-Cafe mailing list