Early feedback: left-biasing `max`

Core Libraries Committee
#21

Apparently so, which is confusing as I thought I had only been following link from you original post. Having said the default max implementation contradict the doc on the hackage version you just pointed.

1 Like
#22

I belatedly went and looked at the proposal. I like the list of options. Notwithstanding the benefits of the first 2 choices, I prefer the 3rd: keep existing behavior and improve the documentation. As currently written, the docs seem to generate n+1 interpretations for every n readers.

4 Likes
#23

I misread the doc (or read the wrong doc) the current doc is left biased even though the implementation is right biased (in agreement with the hakell2010). So indeed either the doc or the implementation need to be changed.

#24

Like in Haskell:

    max x y | x <= y    =  y  
            | otherwise =  x  

 -- max x y = if x <= y then y else x

ā€¦some of the earlier nonstrict functional languages featured right-biased max(imum) functions,

e.g. Lazy ML:

max x y = if x > y then x else y
 --     = if not (x <= y) then x else y
 --     = if x <= y then y else x

and Miranda(R):

max2 a b = a, if a>=b
         = b, otherwise

|| max2 a b = a, if b<=a
||          = b, otherwise

|| max2 a b = b, if a<=b
||          = a, otherwise

(assuming no mistakes, of course!)

To me at least, it seems you have the following options:

  • Now that you know itā€™s been done before in at least two other languages, you can keep looking for the reasons for that choice, as @chreekat suggested, or ask on other forums as youā€™ve done here.

  • The principle of Chestertonā€™s gate fence assumes(!) that the reasons for decisions can always be found in a timely manner. If not, youā€™ll probably have to test the change starting with the GHC sources, then expanding outwards to the rest of the Haskell realm.

  • Alternatively, you can leave a note here for future generations:

    Nitpicks - HaskellWiki

    ā€¦and update the other Haskell documentation (also as @chreekat suggested).

It just depends on how many more resources (personal, computational, etc) youā€™re willing to apply to this effort.

#25

Mirandaā€™s max2 looks left-biased, to me. Thereā€™s a bias flip between the second and third definitions you provided, where you swap a and b everywhere but in the argument list.

Youā€™re right about Lazy ML, and I appreciate the tip to compare notes with other languages in the family from that historical period.

It occurs to me a little belatedly that thereā€™s another option worth considering that would appear on my numbered list of preferences somewhere below (1.) but higher than (4.), though itā€™s the most complicated to explain.

X. Do all of the following:

  • Document max as right-biased, ā€˜for historical reasons unknown to the current generationā€™
  • Change maximum to use flip max instead of max to make maximum left-biased if the underlying Ord has right-biased max
  • Change maximumBy to be left-biased, to match the previous
  • Change the Semigroup instance of Max to use flip max, so that folds using this semigroup are left-biased consistently with the new behavior of maximum and maximumBy
  • Change the Ord instance of Arg to have a right-biased max in compliance with max's new documentation and to preserve the existing left-biased behavior of folding with Arg and Max

Basically, this is the ā€˜if your primary objection is to the behavior of maximum and maximumBy, how could you change those to do the least surprising thing without changing max at all?ā€™ option. The design of Arg implies to me that having consistent left-biased folds was useful to its original author (@ekmett, I believe); this idea is a way to get consistent left-biased maximum folds out of consistent right-biased max members.

#26

Iā€™m not sure I understand the motivation for maximum to be left biaised if max is right biaised. Intuitively maximum [a, b] and max a b should give the same result shoudnā€™t they ?

#27

Sure, which is why my first preference is for max also to be left-biased.

If that canā€™t happen, though, we could uphold the principle that the operations on Foldable structures should act like each other and like find, and all return the first eligible result. Intuitively, maximumBy (\_ _ -> EQ) xs and minimumBy (\_ _ -> EQ) xs should return the same result, shouldnā€™t they? It is just wild to me to think that itā€™s not a big deal for one of those functions to select from the end of the list when the other selects from the start. I get that thereā€™s an explanation for it, once one drills all the way down into how default max is implemented, but nobody should have to do that to have an intuitive understanding of these pretty simple functions.

Compare with maximumBy in vector: ā€˜In case of a tie, the first occurrence wins.ā€™ Compare with the Data.Text API, where functions come in pairs like breakOn and breakOnEndā€”the default, neutrally-named member of the pair is the version that takes action closest to the left. And of course, thereā€™s Arg, which seems unlikely to be used in two-at-a-time comparisons as much as itā€™s used in folds, and has been designed to be left-biased. Coincidence? Accident? Or evidence that a left bias is the intuitive behavior for finding extrema over a data structure?

I think the intuition behind operations on foldable structures favoring their left side is stronger than the intuition behind max a b and maximum [a, b] behaving identically. Though again, my ideal would be for both of them to be left-biased, which would make this whole landscape simpler.

#28

That is your assumption/intuition. One could argue that intuitively getting the min of list is sorting the list and taking the first element. Getting the max is taking the last one of the same list : thatā€™s how you do it physically when getting for example the longuest of bunch of carrots for example. You lay them down and get the last one, not the next to last because the two last seem to be equivalent ā€¦

2 Likes
#29

In the context of software, I think itā€™s very common for a data structure to arrive already ordered by some other propertyā€”perhaps itā€™s important, perhaps it isnā€™t, but if I reverse the sense of a comparison where instead of viewing the greatest element by some metric I want to view the least by that metric, I generally donā€™t want to see the implicit tie-breakerā€”the order in which the values arrivedā€”reversed as well.

Itā€™s a nice mathematical lens to say that the maximum is the end of a sorted list and the minimum is the beginning of that list, but thatā€™s clearly not the best model for the cases where a unique ā€˜sortā€™ isnā€™t defined, which are the scenarios in which bias is relevant.

#30

My point is intuition can largely differs depending on people and backgrounds.
Anyway, I guess at the end of the day, all of this probably doesnā€™t matter much. If people needs such guarantee it is probably easier to make sure that there is no tie to break rather than relying on obscure documentation.

One can easily do fst $ maximum (zip things [1..]) if needs to be.

Funilly enough I am actually working on a bug which I suspect is caused by me assuming that sort is stable (Well it is, but things might not be initially in the order I expect them to be)

#31

As far as I can make out, this convention seems to have been adopted some time between Haskell 1.3 and Haskell 1.4, in case anyone wants to go digging deeper, but I donā€™t see a stated reason in the 1.4 Report.

Before 1.3, the default implementations of min and max were left-biased and only assumed a partial order (using <= and >=). Then Ord was reorganised to assume a total order and use 3-way comparison (compare) for efficiency. There was some talk of removing the operators {(<), (<=), (>), (>=)} from Ord, and also adding new PartialOrd and PreOrd, but those changes didnā€™t make it in.

Edit: I think it may have been copied from an implementation of MOrd by Kevin Atkinson who was writing an STL-alike implementation and thus probably inherited this choice from Alexander Stepanov, who came to this conclusion precisely because of stability, and that it lets you implement sort_2 efficiently as a conditional swap:

template<typename T> // T models TotallyOrdered
inline
void sort_2(T& x, T& y)
{
     if (y < x) swap(x, y);

     assert(x == min(x, y));
     assert(y == max(x, y));
}

[ā€¦] We need to make our min stable:

template<typename T> // T models TotallyOrdered
inline
T& min(T& x, T& y)
{
     return y < x ? y : x;
}

[ā€¦] In order for this condition to hold, max should return the first object
only when it is strictly greater than the second:

template<typename T> // T models TotallyOrdered
inline
T& max(T& x, T& y)
{
     return y < x ? x : y;
}

[ā€¦] We can always obtain the ā€œoldā€ semantics of max by passing the transposed ordering relation to min.

4 Likes
#32

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!

1 Like
#33

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.

1 Like
#34

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.

#35

The argument that people can use flip max works both way. If max is right biaised and people really need a left biaised version , they could also use flip max, what is the problem ?

#36

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.

#37

Do you really mean maximumBy? That doesnā€™t use max at all in its implementation.

#38

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.)

#39

But doesnā€™t then maximumBy . flip do what you want?

(Sorry if Iā€™m missing the point. Iā€™m only half following ā€¦)

#40

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.