[Haskell-cafe] Ultra-newbie Question

[Daniel Fischer]

On Saturday 18 September 2010 22:42:57, Luke Palmer wrote:
> I think this is O(n) time, O(1) space (!).
>
> lastk :: Int -> [a] -> [a]
> lastk k xs = last $ zipWith const (properTails xs) (drop k xs)
>     where properTails = tail . tails
>
> Luke

No, it's O(k) too. You zip [[x_n, x_{n+1}, ... ], ... ] with 
[x_{n+k}, ... ], so all of [x_n, ..., x_{n+k}] stays in memory.

It's *very* nice though, and scales better than my stuff (but my stuff is 
faster for small k [< 1000, here, YMMV]).