[Haskell-cafe] Re: On the verge of ... giving up!
felipe.lessa at gmail.com
Mon Oct 15 07:59:26 EDT 2007
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.
More information about the Haskell-Cafe