[Haskell-cafe] Re: About Fibonacci again...

[Mirko Rahn]

> 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