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

[apfelmus]

Prabhakar Ragde wrote:
>> main n = print . sum . map read . take n . reverse . lines =<< getContents
> Could someone describe succinctly how to compute the space complexity of
> this program, if there are m lines of input and m >> n? Many thanks. --PR

Good point :)

Felipe Lessa wrote:
> 
> main n = print . sum . map read . head . dropWhile (not . null . drop
> n) . tails . lines =<< getContents
> 
> where I changed (take n . reverse) to (head . dropWhile (not . null .
> drop n) . tails). Yes, I cheated, I'm using Data.List =). With this
> version you keep only n lines in memory at any moment, so it has space
> complexity of O(n).

Yes, this has O(n) space complexity since  dropWhile  can discard the 
dropped elements. Unfortunately, we now have O(m*n) time complexity 
since  drop n  is executed for every list element.

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)

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

Regards,
apfelmus


PS: The implementation of  lasts n  in my original version would be

   lasts n = reverse . take n . reverse

But thanks to

   map f . reverse = reverse . map f
   sum . reverse   = sum

we can leave out one reverse.