You have to evaluate the whole input list (absent cheating by checking if you have enough elements equal to minBound), but you don't have to sort more elements than you need to produce, which can save you work.
Yes. Let's say sort here is quicksort (a reasonable choice). Quicksort works, as you know, by partitioning based on a pivot element, putting those smaller before the pivot and those larger after the pivot. It then recursively sorts the two partitions. In Haskell this recursive sort is deferred until the result is actually needed, and a smart haskeller implementing the quicksort would choose to do the smaller-than-pivot partition first--as is the default syntactic choice in any case when concatenating two lists. On each recursion the smaller-than-pivot branch is taken and the larger-than-pivot branch is deferred. As soon as condition is hit where the pivot is the smallest element, it is immediately returned to `take`. The `take` implementation then calls for another value if k>1, and it resumes from where it left of, recursing into the previously deferred larger-than-pivot partition at the bottom of the execution tree, and working itself up from there until `take` is satisfied. Once `k` elements are taken, there's still a partial tree of unexecuted continuations that is thrown away.
In other words, the very nature of Haskell's lazy-by-default semantics makes the straight-forward, seemingly strict implementation of quicksort, or other sorting algorithm, automatically optimized to improve performance through lazy execution.
One was given earlier in the thread: `take 10 . sort`
This should be read from right to left: it sorts an (implicit) list, then reads the first 10 elements from the beginning of the now-sorted list, and throws away the rest.
Except under the hood in Haskell, sort is not a function that takes a list and returns a list. It is a function that takes a list, and returns the smallest element of that list and a function to fetch the rest of the sorted list. (A function which actually returns the second-smallest element and a function that if called returns the third smallest element and another function, etc.)
These ephemeral functions / continuations / "thunks" are allowed to have internal state and thereby perform more complex sorting operations such as quicksort, and might actually be represented by an internal tree of branch points and their returned value or unexecuted thunks.
But all of this complexity is hidden by the compiler. It's not some special property of `sort` either, which might look like this:
sort [] = []
sort (x:xs) = sort small ++ (x : sort large)
where small = [y | y <- xs, y <= x]
large = [y | y <- xs, y > x]
"The sort of an empty list is the empty list. The sort of a non-empty list is the elements of the tail less than or equal to the head of the list, sorted, followed by the head of the list, followed by the elements of the tail greater than the head of the lest, sorted."
The Haskell compiler does the magic of turning this into a lazy-optimized implementation which in the case of `take 10 . sort` doesn't bother to calculate any remaining `sort large` partitions once the first 10 smallest elements have been found.
