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 <p...@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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
