Roberto Zunino wrote:
I actually misread the first one as
Control.Monad.Fix.fix ((1:) . tail . scanl (+) 1)
which is quite nice too, although
map (2^) [0..]
would be much simpler! ;-)
We apply a lesson learned from my last derivation. The lesson was to
look at s!!(n+1).
s = 1 : tail (scanl (+) 1 s)
s!!(n+1) = (1 : tail (scanl (+) 1 s))!!(n+1)
= tail (scanl (+) 1 s) !! n
= scanl (+) 1 s !! (n+1)
= 1 + s!!0 + s!!1 + s!!2 + ... + s!!n
It turns out that we can generalize it a bit to
s!!n = 1 + s!!0 + ... + s!!(n-1)
since, in case n=0, it gives s!!0 = 1 + empty sum, which is still right.
But now plugging the equation of s!!n into that of s!!(n+1) gives
s!!(n+1) = 1 + s!!0 + s!!1 + s!!2 + ... s!!(n-1) + s!!n
= s!!n + s!!n
= 2 * s!!n
Together with s!!0 = 1, this explains why s!!n = 2^n.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
