I'm an absolute Haskell beginner. I got into a discussion recently with a friend about the following line of code:
last $ sort mylist
Would GHC generally optimize this to an O(n) linear search in practice? As a rule of thumb, how do you go about reasoning about compiler optimizations like this?
Thanks in advance!
Edit: fixed tail to last as pointed out by a commenter.
Posted Oct 19, 2018, 5:15 AM UTC · edited
Unfortunately, the kind of optimizations that would work on this particular problem are pretty difficult to reason about. A lot of the time, you'll hear that's because of Haskell's laziness, but I think that's a little misleading. As a beginner, I often remember thinking that laziness could do all kinds of magical things (automatically memoizing stuff, for instance). Laziness is different from what most people are used to, and it's (arguably) harder to internalize than a strict evaluation strategy, but once you learn the rules you can step through the evaluation manually (ie with a pen and paper) and get the correct answer.
But that doesn't apply here! Haskell's sort function is carefully written so that something like take n (sort xs) is O(n log n), rather than O (length xs log length xs), but since you're taking the last element, you do have to pay for sorting the prefix (as far as I can tell from my reading of the function).
Aside from that, though, there are other optimizations that might be at play. Rewrite rules, for instance, are basically rules the programmer can add to spot and optimize things like this: you'd write last (sort xs) = maximum xs (in a REWRITE pragma), and GHC would fire the rule wherever it saw the left-hand-side. As you can imagine, though, these rules are fragile: your syntax (last $ sort xs) is different, so the rule wouldn't even fire on that! Rules also interfere with each other (for instance, last may be rewritten to a fold at some point), and don't play super well with inlining and so on.
Generally speaking, while GHC is very good at optimizing, it's not very consistent. Which means that, in order to figure out if optimizations like this one happen, you've got to do two things: benchmark, and look at the core output (core is the intermediate language produced by GHC after optimizations and so on).
In this case, though, you can be pretty sure that it won't be optimized to maximum. A rewrite rule like last (sort xs) = maximum xs is too fragile and rare that I wouldn't imagine it's in the prelude.
Thanks for the in-depth response. You basically hit all the beats I was wondering about. Basically, it seems like while GHC is very smart, it's not magical, and while Haskell is a lot more declarative than your traditional imperative languages, it's not completely declarative - there's no substitute for good software engineering.
The fact that GHC's behavior and lazy evaluation can be consistently reasoned about like you say makes me a lot more excited for learning Haskell in the future.
As a rule of thumb, how do you go about reasoning about compiler optimizations like this?
This example is not a question of compiler optimization but rather laziness. There's no simple rule of thumb, but Okasaki on functional data structures gives a method for reasoning about the performance of lazy programs.
Generally, I wouldn't rely on the compiler to rewrite last . sort to maximum, but you might look through base to see if any rewrite rules are in place to do this.
Assuming that you mean head, not tail; the main optimization at work here is lazy evaluation. Because you only ever demand the first list element, the sort is only going to be evaluated to the point where you know which list element is the smallest. This will, in practice, amount to traversing the list exactly once (O(n)). If you don't understand why, I recommend writing your own sort and head functions, and doing the evaluation using pen and paper.
Thanks for the input! While that may be true for, say, selection sort, is it really generally true though? Some Googling yields a claim that Haskell uses merge sort, which would need to run the full O(n logn) algorithm to get the first element, which doesn't sound very lazy.
Also, I meant to write last, not tail - sorry about that. In the case of last instead of head, even selection sort wouldn't benefit from lazy evaluation. So is there something else at play here?
Data.List.sort does indeed use a merge sort. If we look at the algorithm, We can conclude that to find the first element, we need O(n) time.
There is only a single bang pattern in the mergesort algorithm in base: when we merge two lists, the resulting list is strictly evaluated to weak head normal form. That means that the first element of each and every sublist to be merged is evaluated the moment you query the first element of the final sorted list. Note that the remainder of the list is left to be lazily evaluated later as required.
The final sorted list is the result of merging two big "1/2 lists" together. To find the minimum of the final list, mergesort only needs the minimum element from each of the "1/2 lists" (we know that this minimum has been strictly evaluated as well). You compare the minimum element from each "half list" to get the final result. In order to get the minimum of a "1/2 list", you need to find the minimum of the two "1/4 lists" and compare them and so on and so forth.
Finding the minimum element in this way takes O(n) comparisons, since every time you do a comparison of a "1/n list", you eliminate a single list from the running, and there are O(n) lists of any length. To find the original sublists in the mergesort algorithm, you must run over the entire unsorted list once to find ascending and descending sequences. This operation takes O(n) time.
So in the current implementation (base-4.12.0.0), It takes O(n) operations to generate sub lists from the unsorted list (for which we already know the minimum), and takes O(n) time to find the minimum value of all of the sublists merged together. Therefore the total running time in O(n).
Note, to find the second element, you only need O(log n) time, which I will leave as an exercise to the reader. Quicksort has similar big-o performance characteristics as mergesort, but the computational complexity is not deterministic, and may perform as slow as O(n^2 )
I see, that's really interesting! I had never heard of a recursively lazy merge sort like this before. I think I'm starting to understand why my friends are so fond of Haskell.
Laziness is both a blessing and a curse. It does enable some super beautiful usages like this though.
Not a compiler optimisation pro, but read about rewrite rules in GHC. My guess is that this would depend upon some rewrite rule getting fired.
Thanks for the pointer, I'll check them out.
It can be O(n) even without rewrite rules, due to laziness.
It is possible to define sort such that last $ sort mylist will be O(n). See "the blueprint technique":
Looks interesting! It's a fair bit over my level at the moment but I've saved the post to re-read later once I have a stronger understanding of what's going on.
Did you mean
head $ sort mylist? Or maybe usinglastinstead oftail?tailis unlikely to change the complexity. As a reminder,tailgives you back a list without the first element. In your example the list still has to be sorted in its entirety which is likely O(n log(n)). :-)For the version with
headthis would become equivalent to the functionminimum.Another comment mentions rewrite rules, I doubt there are rewrite rules for these cases around
sort(but I could be wrong). Depending on the sorting algorithm used, the rest of the list (thetail) might not necessarily need to be sorted thanks to laziness. That is, if the first element of the sorted list is known before the rest of the list is sorted, Haskell will "wait" before sorting the rest of the list until it's needed, which is never in theheadversion.Hope this helps! :-) Tell me if you have any questions.
Sorry, I meant last, not tail! Nice catch. You can see I'm a beginner.