[Haskell-cafe] The C Equiv of != in Haskell miscommunication
thread
Albert Y. C. Lai
trebla at vex.net
Wed May 30 12:01:40 EDT 2007
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.
More information about the Haskell-Cafe
mailing list