Editing The Fibonacci sequence (section)

=== Fibonacci ''n''-Step Numbers ===
The sequence of Fibonacci ''n''-step numbers are formed by summing ''n'' predecessors, using (''n''-1) zeros and a single 1 as starting values:
<math>
  F^{(n)}_k :=
  \begin{cases}
    0             & \mbox{if } 0 \leq k < n-1 \\
    1             & \mbox{if } k = n-1 \\
    \sum\limits_{i=k-n}^{(k-1)} F^{(n)}_i & \mbox{otherwise} \\
   \end{cases}
</math>

Note that the summation in the current definition has a time complexity of ''O(n)'', assuming we memoize previously computed numbers of the sequence. We can do better than. Observe that in the following Tribonacci sequence, we compute the number 81 by summing up 13, 24 and 44:

<math>
F^{(3)} = 0,0,1,1,2,4,7,\underbrace{13,24,44},81,149, \ldots 
</math>

The number 149 is computed in a similar way, but can also be computed as follows:

<math>
149 = 24 + 44 + 81 = (13 + 24 + 44) + 81 - 13 = 81 + 81 - 13 = 2\cdot 81 - 13
</math>

And hence, an equivalent definition of the Fibonacci ''n''-step numbers sequence is:

<math>
  F^{(n)}_k :=
  \begin{cases}
    0             & \mbox{if } 0 \leq k < n-1 \\
    1             & \mbox{if } k = n-1 \\
    1             & \mbox{if } k = n \\
    F^{(n)}_k := 2F^{(n)}_{k-1}-F^{(n)}_{k-(n+1)} & \mbox{otherwise} \\
   \end{cases}
</math>

''(Notice the extra case that is needed)''

Transforming this directly into Haskell gives us:
<haskell>
nfibs n = replicate (n-1) 0 ++ 1 : 1 :
          zipWith (\b a -> 2*b-a) (drop n (nfibs n)) (nfibs n)
</haskell>
This version, however, is slow since the computation of <hask>nfibs n</hask> is not shared. Naming the result using a let-binding and making the lambda pointfree results in:
<haskell>
nfibs n = let r = replicate (n-1) 0 ++ 1 : 1 : zipWith ((-).(2*)) (drop n r) r
          in r
</haskell>