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

[Felipe Lessa]

On 10/14/07, Prabhakar Ragde <plragde at uwaterloo.ca> 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

'reverse' needs to go to the end of the list to start outputting, so
it has to keep all elements in memory somewhere at least in one moment
of time. That means that the program has space complexity of O(m) --
the other functions are all O(1) in terms of line count.

You may try this version instead:

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).

Please anybody correct me if I'm wrong.

Cheers,

-- 
Felipe.