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

Daniil Elovkov daniil.elovkov at googlemail.com
Mon Oct 15 08:49:42 EDT 2007


2007/10/15, Felipe Lessa <felipe.lessa at gmail.com>:
> 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 =).

If we're talking about (more than one)-liners, isn't this simpler to
read? Or is it just me

lasts n xs = let (_,remn) = splitAt n xs in go xs remn

go lag [] = lag
go [] _  = error "shouldn't happen"
go (l:ls) (x:xs) = go ls xs


-- 
Daniil Elovkov


More information about the Haskell-Cafe mailing list