[Haskell-cafe] Time and space complexity of "take k . sort"

[Dan Weston]

Unless of course you use a GHC RULE to rewrite the RHS into the LHS, 
which should always be a valid transformation.

Ketil Malde wrote:
> Paul Johnson <paul at cogito.org.uk> writes:
> 
>>>  takeLargest k = take k . sort
> 
>> But of equal practical interest is the space complexity.  The optimum
>> algorithm is to take the first k items, sort them, and then iterate
>> through the remaining items by adding each item to the sorted list and
>> then throwing out the highest one.  That has space complexity O(k).
>> What does the function above do?
> 
> Well - 'sort' doesn't know the value of 'k', so it needs to retain all
> elements, just in case 'k' might be 'n'.  So I don't see how you can use
> space less than 'n' for a construct like the above.
> 
> -k