Should max()/maxBy()/maxWith() return the last largest element?

#1

Currently, if a collection has more than one instance of the largest element, max(), maxBy() and, maxWith() returns the first one found (like min(), minBy() and, minWith()). I would argue that the right behavior should be to return the last largest element instead of the first one (but Alex Stepanov does a better job explaining why :slight_smile:).

Even one of the example problems provided on “Try Kotlin” seems to support this. On this problem, the code:

fun indexOfMax(a: IntArray): Int? {
    return a.withIndex().maxBy { it.value }?.index
}

won’t pass all the tests, failing on these two cases:

indexOfMax(Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE) is 0, not 2.
indexOfMax(Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE) is 0, not 2.

This can be easily fixed replacing < with <= on the corresponding templates for max, maxBy and maxWith defined in kotlin/libraries/tools/kotlin-stdlib-gen/src/templates/Aggregates.kt.

Is that an oversight or is on purpose?
Should I create a PR for this?

#2

Could you summarize the reasoning from that video?

#3

Ok, I’ll try!

Imagine you have a sorted collection with different elements. Intuitively, the min element should be the first one and the max element should be the last one. min() and max() return the correct object in this case.

Now, imagine that the sorted collection have all instances that are equal. By the same reasoning than before, the min element should still be the first one and the max element, the last one. min() and max() both returns the first one.

In a more theoretical sense, min() and max are different algorithms. You could get the current behavior of max() by using minWith with this greater than comparator:

val greaterThan = object : Comparator<Int> {
    override fun compare(x : Int, y: Int) = y - x
}
val maxElem = a.minWith(greaterThan)

But if you are interested in the last smallest/largest value, you could use max with the changes I proposed (and the appropriated comparator to get the smallest value) .

Usually nobody cares which min or max value do they get… but if you do, I think the expected behavior is not what max currently does (as I mentioned previously with the example from the tutorial).

Alex explanation, although is for C++, is probably clearer and surely better but I hope this briefly covers the main points.

#4

To make it even shorter. What I read what you want is that min and max behave as if you sorted the list with a stable sort algorithm, and then took the first or last elements. (But obviously faster as min/max even in this case can be done in a single pass).

#5

Exactly.

And you really need it, you could always choose to use minWith() or maxWith() with an oposite comparator to get the first largest element or the last smallest element respectively (if you know there could be more than one and the default behavior is not the one you want).

#6

All searching functions (find, etc) return the first match they find, so this is the expected behaviour for min and max. However good your argument might be, it hardly reflects common thinking.

If you want the last maximum to be returned, this should be stated clearly in the code:

listOf(1, 2, 2).asReversed().max()
#7

Reversing a sequence that is not a list can be expensive in that the reverse needs to be stored in memory. Of course the easier solution is to define the comparator such that it defines a full order instead of a partial order (the left is smaller than the right) - just be aware that the validity of that depends on implementation details (in what order are elements compared).

Such a left is smaller than right comparator is not valid for all sorting algorithms or all containers (if they sort) as it does not have the expected reflexivity property.

Most robust is probably to write your own min and max implementations that have the desired behaviour.

#8

list.asReversed() does not take any additional memory or resources. Please see the implementation.

#9

A sequence that is not a list (and therefore does not have random access) needs to basically be stored in a list to be able to reverse it. A key aspect of min and max is that it works on sequences requiring only one memory element (the current min or max element).

#10

Apparently this kind of thinking is more common that you would expect.
As I mentioned in the first post, see this problem and
the tests that it needs to pass (especially testIndexOfMaximum6() and testIndexOfMaximum7()) :slight_smile:

Anyway, as @pdvrieze mentions, asReversed() could be potentially expensive on sequences that can only be iterated using an Iterator object.

#11

This symmetry between min/max and first/last on sorted list looks very convincing.

Could you provide a use case, when it’s crucial to return the last maximum instead of the first?