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.