Re: [Haskell-cafe] Re: On the verge of ... giving up!

On 10/15/07, apfelmus wrote:

Of course, the solution is to first drop n elements and then take tails instead of dropping n elements every time.

map (drop n) . tails = tails . drop n

O(m*n) O(m)

Nice identity. I'll remember this one.

With this, we can write a function that returns the last n elements of a list in O(m) time and O(n) space as

lasts :: Int -> [a] -> [a] lasts n xs = head $ [x | (x,[]) <- zip (tails xs) (tails $ drop n xs)]

and use it as a drop-in replacement

main n = print . sum . map read . lasts n . lines =<< getContents

But that's a a two-liner now heh =). Thanks for your great postings, apfelmus. Cheers, -- Felipe.