Oh wow, yeah, I did not find those earlier Reports before but it’s great to know that they are still out there!
But I’m looking at the link I found for the 1.4 Report, and it gives this implementation:
-- note that (min x y, max x y) = (x,y) or (y,x)
max x y
| x >= y = x
| otherwise = y
min x y
| x < y = x
| otherwise = y
Isn’t that max left-biased and the min right-biased? It appears that between 1.4 and 98 both biases reversed!
I think one justification for left biased min and right biased max is with stable sorting. Even if two elements are the same with regards to Eq and Ord, they can’t be exchanged at will if the stability condition is to be respected. Changing max to be left biased would break that assumption.
Am I missing a known sort function somewhere in the libraries that uses min or max? All of the ones I looked at either delegate to a sortBy compare or go through list sort (which is of the first type).
If there isn’t such a use, then this is strictly a theoretical consideration, as there’s no algorithm that can be implemented with max today that couldn’t be implemented with flip max in my preferred future.
The problem is, still and always, maximumBy, which is more than just a flip away from a version that is consistent with minimumBy. It needs to be either entirely reimplemented, or preceded with a reverse—nontrivial work for either the programmer or the computer, unlike a flip which generally gets optimized away.
Edit: I was wrong: left-biased maximumBy is minimumBy . flip. I would demand to see a clarifying comment around any use of that pattern in one of my projects, but it does rebut my argument.
Do you really mean maximumBy? That doesn’t use max at all in its implementation.
Yes, but it’s written to be right-biased in order to be consistent with maximum (most of the time), which does.
(I also want maximum to be left-biased, of course, but that didn’t serve the argument I was making quite as well because one could write foldl1' (flip max) to get left-biased maximum without too much trouble.)
But doesn’t then maximumBy . flip do what you want?
(Sorry if I’m missing the point. I’m only half following …)
That also inverts the sense of the comparison.
I suppose minimumBy . flip is a good counterargument, though. I… think that’s an unfortunate thing to recommend to someone who is confused why maximumBy doesn’t give a left bias, but it does meet the requirements.
Oh yes, for some reason I was thinking maximumBy took a a -> a -> a which chooses the maximum!
I can absolutely respect that people have different intuitions around the behavior of the binary min and max. But nobody is served by saying that the behavior of minimum and maximum and *By is not predictable. This isn’t an interface where leaving things undefined frees implementers up to make choices that are good for their part of the ecosystem. I’m only calling for change so that things can be more predictable! Who is on the side of unpredictability—who would oppose me by saying no, this shouldn’t change because I would prefer it to be unpredictable? If you like unpredictability so much, change shouldn’t bother you! If you don’t, why object?
I was today years old when I learned that max was right-biased.
I think no matter if you prefer right-bias or left-bias, having clear documentation about the behavior might be a good idea.
If the reactions to this change are split, you could have a function called maxr or maxl as a potential compromise.
Personally, I think max should remain right-biased, only because switching to left-bias might lead to silent breakage.
Would you be equally concerned about silent breaks if we kept max as-is but made Semigroup (Max a), maximum and maximumBy left-biased?
That’s something I can get behind (:
It’s a property of a sorted list that max on any two elements of it taken in the sorted order returns the right hand one. Making max left leaning would break that property because it wouldn’t respect the order given by sort. I think your way of doing it is going to be less intuitive.
It’s a property of a reverse-sorted list that max on any two elements of it taken in the reverse-sorted order returns the left-hand one… except it isn’t, because max happens to be right-biased.
It’s also a property of a reverse-sorted list that min on any two elements of it taken in the reverse-sorted order returns the right-hand one… except it isn’t, because min is left-biased.
The existence of types for which equality is not identity fundamentally causes you to surrender approximately half of all of the statements of the above form that you could imagine making. Is there any practical reason to prefer the ones we have over the ones we’d get by making min and max consistent?
Personally, I don’t think it’s clear that left-biasing max is unambiguously the correct thing to do. I’m pretty happy with max returning the element min didn’t, and as far as maximum and minimum go, if you need a property stronger than “the returned element is greater (or less) than or equal to all other elements in the collection” (for example, that it is the first/last such element), you should be using a different function which is explicit about that.
In addition, even if it was an unambiguously beneficial change, changing the existing behaviour may break existing code in a subtle way. It’s not something like removing fail from Monad where the affected code now has compile errors.
What if changed the description for Ord to stand for total preorders instead of total orders: we allowed a == b = True and a <= b && b <= a = True for distinct a and b? Then the questions like if a sort is stable, or which instance should a function return out of equivalent candidates would be lawful territory instead of unlawful/meaningless.
There’s no order versus preorder confusion here. Relations represented by Ord do have to satisfy antisymmetry—a >= b && b >= a implies a == b.
The fact that a == b doesn’t imply that a is observationally identical to b isn’t represented in the mathematical relational hierarchy, at least not the one involving traditional orders and preorders (maybe a category theorist has a richer toolkit of relation-like things over gadgets defined only up to equivalence or something).
I don’t think that for example (<=) = \x y -> True is a total order on Int, at least in the mathematical terminology. Int with (==) = \x y -> True, (<=) = \x y -> True would be a perfectly fine Ord, if not the description of Ord.
I am not sure what was their intent in the Haskell2010 report, I tried to find instances of Ord that are not total orders, but couldn’t find any.
It definitely is not, given the standard instance of Eq Int. But if you asked me whether, given (==) = \x y -> True, (<=) = \x y -> True defines a total order on Int (or on any other type), I’d have to say yes.