[Haskell-cafe] About Fibonacci again...

[jerzy.karczmarczuk at info.unicaen.fr]

Report from the Rabbit Warren. 

Thank you, everybody, for your contribution. The problem was, how to
construct a one-liner which generates the infinite Rabbit Sequence:
10110101101101011010110110101101101011010110110101101011011010110...
This is the result of an *infinite time* evolution of a system which
iteratively rewrites one young rabbit: 0 -> 1, an old one, and one old:
1 -> 10: itself and a young offspring. The finite sequence after n units
of time fulfils: rs n = rs (n-1) ++ rs (n-2). 

For people beginning to learn Haskell, and having *some* acquaintance
with infinite streams and co-recursive algorithms, this may be a bit
frustrating, because of the "left recursivity", which makes it difficult
to "anchor" the recurrence. But here we have seen plenty of specialists. 

The solution which used the evolution/rewriting operator, needed
\x->if x==0 then [1] else [1,0])
simplified by Andrew Bromage to: \x->1:[0|x==1] .  Very cute!
I will substitute it from now on.
There were two solutions based on it. Ross Paterson: 

rs_rp = let rs = 0 : [x|r<-rs, x <- 1:[0|r==1]] in 1:rs 

Andrew Bromage:
rs_ab = zipWith(!!)(fix(([1]:).map(>>= \x->1:[0|x==1])))[0..] 

This one cheats a bit, fix doesn't belong to the standard, but, well
writing fix f = f (fix f) won't kill anybody. But the complexity of
this algorithm is bad, it seems the slowest one among contributed.
Seems, making an infinite list of infinite lists, and then selecting
the members makes the algorithm quadratic. 

Still, both seem to notice one nice property of the Rabbit Sequence.
If you take any such system: a sequence of symbols, which evolves through
some rewriting, where one symbol may be mapped to many (so the sequence
grows), in general there is no limiting form, you get chaos. Not here!
Rabbits are decent fellows (some Australians may disagree) and the
infinite, ultimate sequence *is a fixed point* of its evolution operator.
This was my solution: 

rs_jk = 1:rq where _:rq = concat (map (\x->1:[0|x==1]) rs_jk) 

This is a bit similar to RP. Those who know the List Monad may try to
squeeze the concat . map into something using >>=, if they wish. 

Mirko Rahn exploited concatMap (I didn't, since when the exercise was
proposed, students didn't know it existed):
rs_mr = limit [[1],[1,0]] [1] where
limit h w = l
  where l = f w ++ f (tail l)
        f = concatMap ((!!) h)
The nice point here is that the same limit function can be used to
generate the sequence of Thue-Morse, which as every patriotic French
child knows, has been invented by P. Prouhet, in 1859...; also some
other sequences may come out of it. But it is not a one-liner, what
an unforgivable shame!
(BTW, Thue wrote his papers in Norwegian only, so patriots from Norway
might disagree with French historians.) 

We see here another cute way of representing the basic rewriting
function! Notice that
((!!) [[1],[1,0]])
is a function which converts 0->1, 1->10. A bit exotic, though... So,
we can easily squeeze the M.R. solution into a specific form 

rs_m1 = f [1] ++ f (tail rs_m1) where f = concatMap (\x->1:[0|x==1])
or simply:
rs_m1 = [1,0] ++ concatMap (\x->1:[0|x==1]) (tail rs_m1)
This is *almost* identical to my solution. 

I have a vague impression that the solution of Alfonso Acosta: 

rs_aa = let acum a1 a2 = a2 ++ acum (a1++a2) a1 in 1 : acum [1] [0] 

is also somehow related to this limit stuff, although it is simpler,
and formulated differently. 

A few minutes ago I read Bernie Pope, who used fix in a similar context,
and concluded that he got the solution of Alfonso Acosta. 

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. 


Finally, Stuart Cook:
fibs' = 1 : 2 : zipWith (+) fibs' (tail fibs')
rs_sc = 1 : 0 : (fibs' >>= flip take rs_sc) 

is a nice way (but in TWO lines, scandalous...) of co-recurring through
this fixed-point, not element by element, but with chunks whose size
increase as the Fibonacci numbers do. 

Thank you once more! 

Jerzy Karczmarczuk