[Haskell-cafe] The C Equiv of != in Haskell miscommunication thread

[Albert Y. C. Lai]

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.