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

Neil Mitchell ndmitchell at gmail.com
Sun Oct 14 17:22:16 EDT 2007


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

The space complexity is the size of the file - i.e. of size m. reverse
will buffer up all the lines before it gives any back, which is a well
known property of reverse. You could rewrite (take n . reverse) as a
function that only requires n lines of buffer.



More information about the Haskell-Cafe mailing list