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

[Felipe Lessa]

On 10/15/07, apfelmus <apfelmus at quantentunnel.de> 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.